1const Range = require('../classes/range.js')
2const Comparator = require('../classes/comparator.js')
3const { ANY } = Comparator
4const satisfies = require('../functions/satisfies.js')
5const 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
43const subset = (sub, dom, options = {}) => {
44  if (sub === dom) {
45    return true
46  }
47
48  sub = new Range(sub, options)
49  dom = new Range(dom, options)
50  let sawNonNull = false
51
52  OUTER: for (const simpleSub of sub.set) {
53    for (const simpleDom of dom.set) {
54      const isSub = simpleSubset(simpleSub, simpleDom, options)
55      sawNonNull = sawNonNull || isSub !== null
56      if (isSub) {
57        continue OUTER
58      }
59    }
60    // the null set is a subset of everything, but null simple ranges in
61    // a complex range should be ignored.  so if we saw a non-null range,
62    // then we know this isn't a subset, but if EVERY simple range was null,
63    // then it is a subset.
64    if (sawNonNull) {
65      return false
66    }
67  }
68  return true
69}
70
71const minimumVersionWithPreRelease = [new Comparator('>=0.0.0-0')]
72const minimumVersion = [new Comparator('>=0.0.0')]
73
74const simpleSubset = (sub, dom, options) => {
75  if (sub === dom) {
76    return true
77  }
78
79  if (sub.length === 1 && sub[0].semver === ANY) {
80    if (dom.length === 1 && dom[0].semver === ANY) {
81      return true
82    } else if (options.includePrerelease) {
83      sub = minimumVersionWithPreRelease
84    } else {
85      sub = minimumVersion
86    }
87  }
88
89  if (dom.length === 1 && dom[0].semver === ANY) {
90    if (options.includePrerelease) {
91      return true
92    } else {
93      dom = minimumVersion
94    }
95  }
96
97  const eqSet = new Set()
98  let gt, lt
99  for (const c of sub) {
100    if (c.operator === '>' || c.operator === '>=') {
101      gt = higherGT(gt, c, options)
102    } else if (c.operator === '<' || c.operator === '<=') {
103      lt = lowerLT(lt, c, options)
104    } else {
105      eqSet.add(c.semver)
106    }
107  }
108
109  if (eqSet.size > 1) {
110    return null
111  }
112
113  let gtltComp
114  if (gt && lt) {
115    gtltComp = compare(gt.semver, lt.semver, options)
116    if (gtltComp > 0) {
117      return null
118    } else if (gtltComp === 0 && (gt.operator !== '>=' || lt.operator !== '<=')) {
119      return null
120    }
121  }
122
123  // will iterate one or zero times
124  for (const eq of eqSet) {
125    if (gt && !satisfies(eq, String(gt), options)) {
126      return null
127    }
128
129    if (lt && !satisfies(eq, String(lt), options)) {
130      return null
131    }
132
133    for (const c of dom) {
134      if (!satisfies(eq, String(c), options)) {
135        return false
136      }
137    }
138
139    return true
140  }
141
142  let higher, lower
143  let hasDomLT, hasDomGT
144  // if the subset has a prerelease, we need a comparator in the superset
145  // with the same tuple and a prerelease, or it's not a subset
146  let needDomLTPre = lt &&
147    !options.includePrerelease &&
148    lt.semver.prerelease.length ? lt.semver : false
149  let needDomGTPre = gt &&
150    !options.includePrerelease &&
151    gt.semver.prerelease.length ? gt.semver : false
152  // exception: <1.2.3-0 is the same as <1.2.3
153  if (needDomLTPre && needDomLTPre.prerelease.length === 1 &&
154      lt.operator === '<' && needDomLTPre.prerelease[0] === 0) {
155    needDomLTPre = false
156  }
157
158  for (const c of dom) {
159    hasDomGT = hasDomGT || c.operator === '>' || c.operator === '>='
160    hasDomLT = hasDomLT || c.operator === '<' || c.operator === '<='
161    if (gt) {
162      if (needDomGTPre) {
163        if (c.semver.prerelease && c.semver.prerelease.length &&
164            c.semver.major === needDomGTPre.major &&
165            c.semver.minor === needDomGTPre.minor &&
166            c.semver.patch === needDomGTPre.patch) {
167          needDomGTPre = false
168        }
169      }
170      if (c.operator === '>' || c.operator === '>=') {
171        higher = higherGT(gt, c, options)
172        if (higher === c && higher !== gt) {
173          return false
174        }
175      } else if (gt.operator === '>=' && !satisfies(gt.semver, String(c), options)) {
176        return false
177      }
178    }
179    if (lt) {
180      if (needDomLTPre) {
181        if (c.semver.prerelease && c.semver.prerelease.length &&
182            c.semver.major === needDomLTPre.major &&
183            c.semver.minor === needDomLTPre.minor &&
184            c.semver.patch === needDomLTPre.patch) {
185          needDomLTPre = false
186        }
187      }
188      if (c.operator === '<' || c.operator === '<=') {
189        lower = lowerLT(lt, c, options)
190        if (lower === c && lower !== lt) {
191          return false
192        }
193      } else if (lt.operator === '<=' && !satisfies(lt.semver, String(c), options)) {
194        return false
195      }
196    }
197    if (!c.operator && (lt || gt) && gtltComp !== 0) {
198      return false
199    }
200  }
201
202  // if there was a < or >, and nothing in the dom, then must be false
203  // UNLESS it was limited by another range in the other direction.
204  // Eg, >1.0.0 <1.0.1 is still a subset of <2.0.0
205  if (gt && hasDomLT && !lt && gtltComp !== 0) {
206    return false
207  }
208
209  if (lt && hasDomGT && !gt && gtltComp !== 0) {
210    return false
211  }
212
213  // we needed a prerelease range in a specific tuple, but didn't get one
214  // then this isn't a subset.  eg >=1.2.3-pre is not a subset of >=1.0.0,
215  // because it includes prereleases in the 1.2.3 tuple
216  if (needDomGTPre || needDomLTPre) {
217    return false
218  }
219
220  return true
221}
222
223// >=1.2.3 is lower than >1.2.3
224const higherGT = (a, b, options) => {
225  if (!a) {
226    return b
227  }
228  const comp = compare(a.semver, b.semver, options)
229  return comp > 0 ? a
230    : comp < 0 ? b
231    : b.operator === '>' && a.operator === '>=' ? b
232    : a
233}
234
235// <=1.2.3 is higher than <1.2.3
236const lowerLT = (a, b, options) => {
237  if (!a) {
238    return b
239  }
240  const comp = compare(a.semver, b.semver, options)
241  return comp < 0 ? a
242    : comp > 0 ? b
243    : b.operator === '<' && a.operator === '<=' ? b
244    : a
245}
246
247module.exports = subset
248