Thank you

[jandockx]

After 2 longs days of searching and dispair, your library seems to save me. Thank you.

I am a bit worried about the viability, though, seeing your previous responses. Is this a dead project for you, or would you still consider taking PRs, and releasing new versions?

Context

I am in need to determine whether a first pattern raa is covered by another ram.

Interesting references I found are:

• Determining whether a regex is a subset of another
• The Inclusion Problem for Regular Expressions
• Does an algorithm exist which can determine whether one regular language matches any input another regular language matches?
• Testing the Equivalence of Regular Languages
• Is one regular language subset of another? (seems to be an approach that is not as good as the others)
• Algorithm to find out whether the matches for two Glob patterns (or Regular Expressions) intersect

The approach that I found referenced was

1. create ram|raa, the pattern that expresses that a string must match ram or raa
2. derive DFA(ram|raa) and DFA(ram), and minimize them
3. if the 2 resulting minimized DFAs are isomorph, raa is covered by ram

Indeed, ram|raa (ram or raa) allows more strings to match than ram alone. If however ram|raa turns out to match exactly the same set of strings as ram alone, it means that all the strings that are matched by raa are already in the set of strings matched by ram, i.e., raa is covered by ram.

Alternatively, we can determine the intersection of raa and ram:

1. create ram&raa, the pattern that expresses that a string must match both ram and raa
2. derive DFA(ram&raa) and DFA(raa), and minimize them
3. if the 2 resulting minimized [DFA]s are isomorph, raa is covered by ram

Indeed, ram&raa (ram and raa) allows less strings to match than raa alone. If however ram&raa turns out to match exactly the same set of strings as raa alone, it means that there are no strings that are matched by raa that are not matched by ram, i.e., raa is covered by ram.

This now seems to be realised trivially by your library:

const intersect = require('glob-intersection')

function minimize (pattern) {
  return intersect(pattern, pattern)
}

function covered (raaPattern, ramPattern) {
  let intersection = intersect(raaPattern, ramPattern)
  console.log(`${raaPattern} ∩ ${ramPattern} = ${intersection}`)
  const result = typeof intersection === 'string' && intersection === minimize(raaPattern)
  console.log(`${raaPattern} ⊆ ${ramPattern} ? ${result}`)
  return result
}

covered('/I/*/p523564.faa.bar.baz/**', '/I/**')
covered('/I/**', '/I/*/p523564.faa.bar.baz/**')
covered('/I/*/p523564.faa.bar.baz/**', '/I/*')
covered('/I/*/p523564.faa.bar.baz/service/instance', '/I/host/p523564.faa.bar.baz/**')

covered('{GET,PUT,DELETE}', '*')
covered('*', '{GET,PUT,DELETE}')
covered('PUT', 'DELETE')
covered('PUT', '{GET,DELETE}')
covered('{GET,PUT}', '{GET,PUT,DELETE}') // requires minimisation of raaPattern

[guncha]

Glad you found it useful, @jandockx. We don't currently use it at @Pathgather, but it was a fun little project so I would personally consider PRs and releasing new versions. Let me know if you need any further help.

[jandockx]

I've hit a snag. The output of intersection is not normalized, which means that I cannot compare the intersection with raaPattern for equivalence. My 'minimize' doesn't normalize.

const a = '{a/1,a/2}'
const b = '{a/2,a/1}'
const c = 'a/{2,1}'

console.log(intersect(a, a)) // {a/1,a/2}
console.log(intersect(b, b)) // {a/2,a/1}
console.log(intersect(c, c)) // a/{1,2}
console.log(intersect(a, b)) // {a/1,a/2}
console.log(intersect(b, a)) // {a/2,a/1}
console.log(intersect(a, c)) // {a/1,a/2}
console.log(intersect(c, a)) // {a/1,a/2}

This means my test intersection === minimize(raaPattern) does not work. It is false for some equivalent patterns.

console.log(intersect('a/{1,2}', '{a/1,a/2}')) // {a/1,a/2}
console.log(intersect('{a/1,a/2}', 'a/{1,2}')) // {a/1,a/2}
console.log(covered('{a/1,a/2}', 'a/{1,2}')) // true, intersection is {a/1,a/2}
console.log(covered('a/{1,2}', '{a/1,a/2}')) // false, because the intersection is {a/1,a/2}, but raaPattern is a/{1,2}

Any ideas?

[jandockx]

Also

const alpha = 'a/{1,2}'
const beta = '{a/1,a/2}'
const i = intersect(alpha, beta)
console.log('i', i)
const u = `{${alpha},${beta}}`
console.log('u', u)
const ui = intersect(u, i)
console.log('ui', ui)
const uAlpha = intersect(u, alpha)
console.log('uAlpha', uAlpha)
console.log('uAlpha alpha', intersect(uAlpha, alpha))
console.log('uAlpha beta', intersect(uAlpha, beta))

Gives output

i {a/1,a/2}
u {a/{1,2},{a/1,a/2}}
ui {a/1,a/2}
uAlpha {a/{1,2},a/1,a/2}
uAlpha alpha {a/{1,2},a/1,a/2}
uAlpha beta {a/1,a/2}

'uAlpha' and 'uAlpha alpha' are weird, and the fact that uAlpha is different is weirder.