summaryrefslogtreecommitdiff
path: root/sources/scala/tools/nsc/transform/OverridingPairs.scala
blob: 2f80216dbe48077f2e0948d0629f5f400e31dac4 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* NSC -- new scala compiler
 * Copyright 2005 LAMP/EPFL
 * @author
 */
// $Id$
package scala.tools.nsc.transform;

import util.HashSet;
import collection.mutable.HashMap;
import symtab.Flags._;

abstract class OverridingPairs {

  val global: Global;
  import global._;

  class Cursor(base: Symbol) {

    private val self = base.thisType;

    protected def exclude(sym: Symbol): boolean = sym.isConstructor || (sym hasFlag LOCAL);

    protected def parents: List[Type] = base.info.parents;

    protected def matches(sym1: Symbol, sym2: Symbol): boolean =
      sym1.isType || (self.memberType(sym1) matches self.memberType(sym2));

    private type BitSet = Array[int];

    private def newBitSet(size: int): BitSet = new Array((size + 31) >> 5);

    private def include(bs: BitSet, n: int): unit = {
      val nshifted = n >> 5;
      val nmask = 1 << (n & 31);
      bs(nshifted) = bs(nshifted) | nmask
    }

    private def intersectionContainsElementLeq(bs1: BitSet, bs2: BitSet, n: int): boolean = {
      val nshifted = n >> 5;
      val nmask = 1 << (n & 31);
      ((List.range(0, nshifted) exists (i => (bs1(i) & bs2(i)) != 0)) ||
       ((bs1(nshifted) & bs2(nshifted) & (nmask | nmask - 1)) != 0))
    }

    private val decls = new Scope;
    { def fillDecls(bcs: List[Symbol], deferredflag: int): unit =
        if (!bcs.isEmpty) {
	  fillDecls(bcs.tail, deferredflag);
	  var e = bcs.head.info.decls.elems;
	  while (e != null) {
	    if (e.sym.getFlag(DEFERRED) == deferredflag && !exclude(e.sym)) decls enter e.sym;
	    e = e.next
	  }
	}
      fillDecls(base.info.baseClasses, DEFERRED);
      fillDecls(base.info.baseClasses, 0);
    }

    private val size = base.info.baseClasses.length;

    private val index = new HashMap[Symbol, int];
    { var i = 0;
      for (val bc <- base.info.baseClasses) {
	index(bc) = i;
	i = i + 1
      }
    }

    private val subParents = new Array[BitSet](size);
    { for (val i <- List.range(0, size))
	subParents(i) = new BitSet(size);
      for (val p <- parents) {
        val pIndex = index(p.symbol);
        for (val bc <- p.baseClasses) include(subParents(index(bc)), pIndex);
      }
    }


    private def hasCommonParent(sym1: Symbol, sym2: Symbol) = {
      //assert(index.get(sym1.owner) != None, "" + base + " " + sym1 + " " + sym1.owner);//DEBUG
      //assert(index.get(sym2.owner) != None, "" + base + " " + sym2 + " " + sym2.owner);//DEBUG
      val index1 = index(sym1.owner);
      val index2 = index(sym2.owner);
      val minindex = if (index1 < index2) index1 else index2;
      intersectionContainsElementLeq(subParents(index1), subParents(index2), minindex)
    }

    private val visited = new HashSet[ScopeEntry](256);
    private var curEntry = decls.elems;
    private var nextEntry = curEntry;

    var overriding: Symbol = _;
    var overridden: Symbol = _;

    def hasNext: boolean = curEntry != null;

    def next: unit =
      if (curEntry != null) {
	overriding = curEntry.sym;
	if (nextEntry != null) {
	  do {
	    nextEntry = decls.lookupNextEntry(nextEntry);
	  } while (nextEntry != null &&
		   ((nextEntry.sym hasFlag PRIVATE) ||
		    (overriding.owner == nextEntry.sym.owner) ||
		    (hasCommonParent(overriding, nextEntry.sym)) ||
		    (!matches(overriding, nextEntry.sym)) ||
		    (overriding hasFlag LOCAL)))
	}
	if (nextEntry != null) {
	  overridden = nextEntry.sym;
	  //System.out.println("yield: " + overriding + overriding.locationString + " / " + overridden + overridden.locationString);//DEBUG
	  visited addEntry nextEntry
	} else {
	  do {
	    curEntry = curEntry.next
	  } while (curEntry != null && (visited contains curEntry));
	  nextEntry = curEntry;
	  next
	}
      }

    next
  }
}