diff options
Diffstat (limited to 'compiler/nimsets.nim')
| -rw-r--r-- | compiler/nimsets.nim | 177 |
1 files changed, 79 insertions, 98 deletions
diff --git a/compiler/nimsets.nim b/compiler/nimsets.nim index 94507adf0..7edf55278 100644 --- a/compiler/nimsets.nim +++ b/compiler/nimsets.nim @@ -10,167 +10,148 @@ # this unit handles Nim sets; it implements symbolic sets import - ast, astalgo, trees, nversion, msgs, platform, bitsets, types, renderer - -proc toBitSet*(s: PNode, b: var TBitSet) - # this function is used for case statement checking: -proc overlap*(a, b: PNode): bool -proc inSet*(s: PNode, elem: PNode): bool -proc someInSet*(s: PNode, a, b: PNode): bool -proc emptyRange*(a, b: PNode): bool -proc setHasRange*(s: PNode): bool - # returns true if set contains a range (needed by the code generator) - # these are used for constant folding: -proc unionSets*(a, b: PNode): PNode -proc diffSets*(a, b: PNode): PNode -proc intersectSets*(a, b: PNode): PNode -proc symdiffSets*(a, b: PNode): PNode -proc containsSets*(a, b: PNode): bool -proc equalSets*(a, b: PNode): bool -proc cardSet*(s: PNode): BiggestInt -# implementation - -proc inSet(s: PNode, elem: PNode): bool = + ast, astalgo, lineinfos, bitsets, types, options + +when defined(nimPreviewSlimSystem): + import std/assertions + +proc inSet*(s: PNode, elem: PNode): bool = + assert s.kind == nkCurly if s.kind != nkCurly: - internalError(s.info, "inSet") + #internalError(s.info, "inSet") return false - for i in countup(0, sonsLen(s) - 1): - if s.sons[i].kind == nkRange: - if leValue(s.sons[i].sons[0], elem) and - leValue(elem, s.sons[i].sons[1]): + for i in 0..<s.len: + if s[i].kind == nkRange: + if leValue(s[i][0], elem) and + leValue(elem, s[i][1]): return true else: - if sameValue(s.sons[i], elem): + if sameValue(s[i], elem): return true result = false -proc overlap(a, b: PNode): bool = +proc overlap*(a, b: PNode): bool = if a.kind == nkRange: if b.kind == nkRange: # X..Y and C..D overlap iff (X <= D and C <= Y) - result = leValue(a.sons[0], b.sons[1]) and - leValue(b.sons[0], a.sons[1]) + result = leValue(a[0], b[1]) and + leValue(b[0], a[1]) else: - result = leValue(a.sons[0], b) and leValue(b, a.sons[1]) + result = leValue(a[0], b) and leValue(b, a[1]) else: if b.kind == nkRange: - result = leValue(b.sons[0], a) and leValue(a, b.sons[1]) + result = leValue(b[0], a) and leValue(a, b[1]) else: result = sameValue(a, b) -proc someInSet(s: PNode, a, b: PNode): bool = +proc someInSet*(s: PNode, a, b: PNode): bool = # checks if some element of a..b is in the set s + assert s.kind == nkCurly if s.kind != nkCurly: - internalError(s.info, "SomeInSet") + #internalError(s.info, "SomeInSet") return false - for i in countup(0, sonsLen(s) - 1): - if s.sons[i].kind == nkRange: - if leValue(s.sons[i].sons[0], b) and leValue(b, s.sons[i].sons[1]) or - leValue(s.sons[i].sons[0], a) and leValue(a, s.sons[i].sons[1]): + for i in 0..<s.len: + if s[i].kind == nkRange: + if leValue(s[i][0], b) and leValue(b, s[i][1]) or + leValue(s[i][0], a) and leValue(a, s[i][1]): return true else: # a <= elem <= b - if leValue(a, s.sons[i]) and leValue(s.sons[i], b): + if leValue(a, s[i]) and leValue(s[i], b): return true result = false -proc toBitSet(s: PNode, b: var TBitSet) = - var first, j: BiggestInt - first = firstOrd(s.typ.sons[0]) - bitSetInit(b, int(getSize(s.typ))) - for i in countup(0, sonsLen(s) - 1): - if s.sons[i].kind == nkRange: - j = getOrdValue(s.sons[i].sons[0]) - while j <= getOrdValue(s.sons[i].sons[1]): - bitSetIncl(b, j - first) +proc toBitSet*(conf: ConfigRef; s: PNode): TBitSet = + result = @[] + var first: Int128 = Zero + var j: Int128 = Zero + first = firstOrd(conf, s.typ.elementType) + bitSetInit(result, int(getSize(conf, s.typ))) + for i in 0..<s.len: + if s[i].kind == nkRange: + j = getOrdValue(s[i][0], first) + while j <= getOrdValue(s[i][1], first): + bitSetIncl(result, toInt64(j - first)) inc(j) else: - bitSetIncl(b, getOrdValue(s.sons[i]) - first) + bitSetIncl(result, toInt64(getOrdValue(s[i]) - first)) -proc toTreeSet(s: TBitSet, settype: PType, info: TLineInfo): PNode = +proc toTreeSet*(conf: ConfigRef; s: TBitSet, settype: PType, info: TLineInfo): PNode = var a, b, e, first: BiggestInt # a, b are interval borders elemType: PType n: PNode - elemType = settype.sons[0] - first = firstOrd(elemType) + elemType = settype[0] + first = firstOrd(conf, elemType).toInt64 result = newNodeI(nkCurly, info) result.typ = settype result.info = info e = 0 - while e < len(s) * ElemSize: + while e < s.len * ElemSize: if bitSetIn(s, e): a = e b = e while true: inc(b) - if (b >= len(s) * ElemSize) or not bitSetIn(s, b): break + if (b >= s.len * ElemSize) or not bitSetIn(s, b): break dec(b) - let aa = newIntTypeNode(nkIntLit, a + first, elemType) + let aa = newIntTypeNode(a + first, elemType) aa.info = info if a == b: - addSon(result, aa) + result.add aa else: n = newNodeI(nkRange, info) n.typ = elemType - addSon(n, aa) - let bb = newIntTypeNode(nkIntLit, b + first, elemType) + n.add aa + let bb = newIntTypeNode(b + first, elemType) bb.info = info - addSon(n, bb) - addSon(result, n) + n.add bb + result.add n e = b inc(e) template nodeSetOp(a, b: PNode, op: untyped) {.dirty.} = - var x, y: TBitSet - toBitSet(a, x) - toBitSet(b, y) + var x = toBitSet(conf, a) + let y = toBitSet(conf, b) op(x, y) - result = toTreeSet(x, a.typ, a.info) + result = toTreeSet(conf, x, a.typ, a.info) -proc unionSets(a, b: PNode): PNode = nodeSetOp(a, b, bitSetUnion) -proc diffSets(a, b: PNode): PNode = nodeSetOp(a, b, bitSetDiff) -proc intersectSets(a, b: PNode): PNode = nodeSetOp(a, b, bitSetIntersect) -proc symdiffSets(a, b: PNode): PNode = nodeSetOp(a, b, bitSetSymDiff) +proc unionSets*(conf: ConfigRef; a, b: PNode): PNode = nodeSetOp(a, b, bitSetUnion) +proc diffSets*(conf: ConfigRef; a, b: PNode): PNode = nodeSetOp(a, b, bitSetDiff) +proc intersectSets*(conf: ConfigRef; a, b: PNode): PNode = nodeSetOp(a, b, bitSetIntersect) +proc symdiffSets*(conf: ConfigRef; a, b: PNode): PNode = nodeSetOp(a, b, bitSetSymDiff) -proc containsSets(a, b: PNode): bool = - var x, y: TBitSet - toBitSet(a, x) - toBitSet(b, y) +proc containsSets*(conf: ConfigRef; a, b: PNode): bool = + let x = toBitSet(conf, a) + let y = toBitSet(conf, b) result = bitSetContains(x, y) -proc equalSets(a, b: PNode): bool = - var x, y: TBitSet - toBitSet(a, x) - toBitSet(b, y) +proc equalSets*(conf: ConfigRef; a, b: PNode): bool = + let x = toBitSet(conf, a) + let y = toBitSet(conf, b) result = bitSetEquals(x, y) -proc complement*(a: PNode): PNode = - var x: TBitSet - toBitSet(a, x) - for i in countup(0, high(x)): x[i] = not x[i] - result = toTreeSet(x, a.typ, a.info) - -proc cardSet(s: PNode): BiggestInt = - # here we can do better than converting it into a compact set - # we just count the elements directly - result = 0 - for i in countup(0, sonsLen(s) - 1): - if s.sons[i].kind == nkRange: - result = result + getOrdValue(s.sons[i].sons[1]) - - getOrdValue(s.sons[i].sons[0]) + 1 - else: - inc(result) +proc complement*(conf: ConfigRef; a: PNode): PNode = + var x = toBitSet(conf, a) + for i in 0..high(x): x[i] = not x[i] + result = toTreeSet(conf, x, a.typ, a.info) -proc setHasRange(s: PNode): bool = +proc deduplicate*(conf: ConfigRef; a: PNode): PNode = + let x = toBitSet(conf, a) + result = toTreeSet(conf, x, a.typ, a.info) + +proc cardSet*(conf: ConfigRef; a: PNode): BiggestInt = + let x = toBitSet(conf, a) + result = bitSetCard(x) + +proc setHasRange*(s: PNode): bool = + assert s.kind == nkCurly if s.kind != nkCurly: - internalError(s.info, "SetHasRange") return false - for i in countup(0, sonsLen(s) - 1): - if s.sons[i].kind == nkRange: + for i in 0..<s.len: + if s[i].kind == nkRange: return true result = false -proc emptyRange(a, b: PNode): bool = +proc emptyRange*(a, b: PNode): bool = result = not leValue(a, b) # a > b iff not (a <= b) - |