1  const Range = require('../classes/range.js')
  2  const Comparator = require('../classes/comparator.js')
  3  const { ANY } = Comparator
  4  const satisfies = require('../functions/satisfies.js')
  5  const compare = require('../functions/compare.js')
  6  
  7  // Complex range `r1 || r2 || ...` is a subset of `R1 || R2 || ...` iff:
  8  // - Every simple range `r1, r2, ...` is a null set, OR
  9  // - Every simple range `r1, r2, ...` which is not a null set is a subset of
 10  //   some `R1, R2, ...`
 11  //
 12  // Simple range `c1 c2 ...` is a subset of simple range `C1 C2 ...` iff:
 13  // - If c is only the ANY comparator
 14  //   - If C is only the ANY comparator, return true
 15  //   - Else if in prerelease mode, return false
 16  //   - else replace c with `[>=0.0.0]`
 17  // - If C is only the ANY comparator
 18  //   - if in prerelease mode, return true
 19  //   - else replace C with `[>=0.0.0]`
 20  // - Let EQ be the set of = comparators in c
 21  // - If EQ is more than one, return true (null set)
 22  // - Let GT be the highest > or >= comparator in c
 23  // - Let LT be the lowest < or <= comparator in c
 24  // - If GT and LT, and GT.semver > LT.semver, return true (null set)
 25  // - If any C is a = range, and GT or LT are set, return false
 26  // - If EQ
 27  //   - If GT, and EQ does not satisfy GT, return true (null set)
 28  //   - If LT, and EQ does not satisfy LT, return true (null set)
 29  //   - If EQ satisfies every C, return true
 30  //   - Else return false
 31  // - If GT
 32  //   - If GT.semver is lower than any > or >= comp in C, return false
 33  //   - If GT is >=, and GT.semver does not satisfy every C, return false
 34  //   - If GT.semver has a prerelease, and not in prerelease mode
 35  //     - If no C has a prerelease and the GT.semver tuple, return false
 36  // - If LT
 37  //   - If LT.semver is greater than any < or <= comp in C, return false
 38  //   - If LT is <=, and LT.semver does not satisfy every C, return false
 39  //   - If GT.semver has a prerelease, and not in prerelease mode
 40  //     - If no C has a prerelease and the LT.semver tuple, return false
 41  // - Else return true
 42  
 43  const subset = (sub, dom, options = {}) => {
 44    if (sub === dom)
 45      return true
 46  
 47    sub = new Range(sub, options)
 48    dom = new Range(dom, options)
 49    let sawNonNull = false
 50  
 51    OUTER: for (const simpleSub of sub.set) {
 52      for (const simpleDom of dom.set) {
 53        const isSub = simpleSubset(simpleSub, simpleDom, options)
 54        sawNonNull = sawNonNull || isSub !== null
 55        if (isSub)
 56          continue OUTER
 57      }
 58      // the null set is a subset of everything, but null simple ranges in
 59      // a complex range should be ignored.  so if we saw a non-null range,
 60      // then we know this isn't a subset, but if EVERY simple range was null,
 61      // then it is a subset.
 62      if (sawNonNull)
 63        return false
 64    }
 65    return true
 66  }
 67  
 68  const simpleSubset = (sub, dom, options) => {
 69    if (sub === dom)
 70      return true
 71  
 72    if (sub.length === 1 && sub[0].semver === ANY) {
 73      if (dom.length === 1 && dom[0].semver === ANY)
 74        return true
 75      else if (options.includePrerelease)
 76        sub = [ new Comparator('>=0.0.0-0') ]
 77      else
 78        sub = [ new Comparator('>=0.0.0') ]
 79    }
 80  
 81    if (dom.length === 1 && dom[0].semver === ANY) {
 82      if (options.includePrerelease)
 83        return true
 84      else
 85        dom = [ new Comparator('>=0.0.0') ]
 86    }
 87  
 88    const eqSet = new Set()
 89    let gt, lt
 90    for (const c of sub) {
 91      if (c.operator === '>' || c.operator === '>=')
 92        gt = higherGT(gt, c, options)
 93      else if (c.operator === '<' || c.operator === '<=')
 94        lt = lowerLT(lt, c, options)
 95      else
 96        eqSet.add(c.semver)
 97    }
 98  
 99    if (eqSet.size > 1)
100      return null
101  
102    let gtltComp
103    if (gt && lt) {
104      gtltComp = compare(gt.semver, lt.semver, options)
105      if (gtltComp > 0)
106        return null
107      else if (gtltComp === 0 && (gt.operator !== '>=' || lt.operator !== '<='))
108        return null
109    }
110  
111    // will iterate one or zero times
112    for (const eq of eqSet) {
113      if (gt && !satisfies(eq, String(gt), options))
114        return null
115  
116      if (lt && !satisfies(eq, String(lt), options))
117        return null
118  
119      for (const c of dom) {
120        if (!satisfies(eq, String(c), options))
121          return false
122      }
123  
124      return true
125    }
126  
127    let higher, lower
128    let hasDomLT, hasDomGT
129    // if the subset has a prerelease, we need a comparator in the superset
130    // with the same tuple and a prerelease, or it's not a subset
131    let needDomLTPre = lt &&
132      !options.includePrerelease &&
133      lt.semver.prerelease.length ? lt.semver : false
134    let needDomGTPre = gt &&
135      !options.includePrerelease &&
136      gt.semver.prerelease.length ? gt.semver : false
137    // exception: <1.2.3-0 is the same as <1.2.3
138    if (needDomLTPre && needDomLTPre.prerelease.length === 1 &&
139        lt.operator === '<' && needDomLTPre.prerelease[0] === 0) {
140      needDomLTPre = false
141    }
142  
143    for (const c of dom) {
144      hasDomGT = hasDomGT || c.operator === '>' || c.operator === '>='
145      hasDomLT = hasDomLT || c.operator === '<' || c.operator === '<='
146      if (gt) {
147        if (needDomGTPre) {
148          if (c.semver.prerelease && c.semver.prerelease.length &&
149              c.semver.major === needDomGTPre.major &&
150              c.semver.minor === needDomGTPre.minor &&
151              c.semver.patch === needDomGTPre.patch) {
152            needDomGTPre = false
153          }
154        }
155        if (c.operator === '>' || c.operator === '>=') {
156          higher = higherGT(gt, c, options)
157          if (higher === c && higher !== gt)
158            return false
159        } else if (gt.operator === '>=' && !satisfies(gt.semver, String(c), options))
160          return false
161      }
162      if (lt) {
163        if (needDomLTPre) {
164          if (c.semver.prerelease && c.semver.prerelease.length &&
165              c.semver.major === needDomLTPre.major &&
166              c.semver.minor === needDomLTPre.minor &&
167              c.semver.patch === needDomLTPre.patch) {
168            needDomLTPre = false
169          }
170        }
171        if (c.operator === '<' || c.operator === '<=') {
172          lower = lowerLT(lt, c, options)
173          if (lower === c && lower !== lt)
174            return false
175        } else if (lt.operator === '<=' && !satisfies(lt.semver, String(c), options))
176          return false
177      }
178      if (!c.operator && (lt || gt) && gtltComp !== 0)
179        return false
180    }
181  
182    // if there was a < or >, and nothing in the dom, then must be false
183    // UNLESS it was limited by another range in the other direction.
184    // Eg, >1.0.0 <1.0.1 is still a subset of <2.0.0
185    if (gt && hasDomLT && !lt && gtltComp !== 0)
186      return false
187  
188    if (lt && hasDomGT && !gt && gtltComp !== 0)
189      return false
190  
191    // we needed a prerelease range in a specific tuple, but didn't get one
192    // then this isn't a subset.  eg >=1.2.3-pre is not a subset of >=1.0.0,
193    // because it includes prereleases in the 1.2.3 tuple
194    if (needDomGTPre || needDomLTPre)
195      return false
196  
197    return true
198  }
199  
200  // >=1.2.3 is lower than >1.2.3
201  const higherGT = (a, b, options) => {
202    if (!a)
203      return b
204    const comp = compare(a.semver, b.semver, options)
205    return comp > 0 ? a
206      : comp < 0 ? b
207      : b.operator === '>' && a.operator === '>=' ? b
208      : a
209  }
210  
211  // <=1.2.3 is higher than <1.2.3
212  const lowerLT = (a, b, options) => {
213    if (!a)
214      return b
215    const comp = compare(a.semver, b.semver, options)
216    return comp < 0 ? a
217      : comp > 0 ? b
218      : b.operator === '<' && a.operator === '<=' ? b
219      : a
220  }
221  
222  module.exports = subset