subset.js 7.1 KB

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