Object-Oriented Metrics: The CK Suite

DIT, Depth of Inheritance Tree. How far the class is from the root of its hierarchy; with multiple inheritance, "the maximum length from the node to the root of the tree". "DIT is a measure of how many ancestor classes can potentially affect this class." A deep class inherits much, "making it more complex to predict its behavior", and deeper trees mean "greater design complexity"; but "the greater the potential reuse of inherited methods".

NOC, Number of Children. The immediate subclasses. More children mean more reuse, but also "the greater the likelihood of improper abstraction of the parent class", and for the tester: "If a class has a large number of children, it may require more testing of the methods in that class."

CBO, Coupling Between Object classes. "Two classes are coupled when methods declared in one class use methods or instance variables defined by the other class." The viewpoints are all warnings: "Excessive coupling between object classes is detrimental to modular design and prevents reuse", and "The higher the inter-object class coupling, the more rigorous the testing needs to be."

RFC, Response For a Class. The response set is the class's own methods together with every method they call: the set {M} of the class's methods joined with every {Ri}, where {Ri} is the set of methods called by method i, counted "only up to the first level of nesting of method calls". RFC is the size of that set. "If a large number of methods can be invoked in response to a message, the testing and debugging of the class becomes more complicated", and "A worst case value for possible responses will assist in appropriate allocation of testing time."

LCOM, Lack of Cohesion in Methods. For each method, take the set of instance variables it uses. Count the pairs of methods whose sets have nothing in common (P) and the pairs that share at least one (Q). LCOM is P minus Q if that is positive, and 0 otherwise. The paper's example: methods using {a, b, c, d, e}, {a, b, e} and {x, y, z} give two disjoint pairs and one sharing pair, so "LCOM is the (number of null intersections - number of non-empty intersections), which in this case is 1." A high LCOM is a design finding: "Lack of cohesion implies classes should probably be split into two or more sub-classes."

Worked example: measuring ExamReg's form classes

ExamReg's forms are classes: a base Form, an ExamForm for the examination form, a BacklogForm for students registering only backlog papers, and a ContactForm for updating a phone number, with two helpers, Catalogue and FeeRule.

class Form:
    def __init__(self, student):
        self.student = student
        self.errors = []

    def validate(self):
        if not self.student.roll_no:
            self.errors.append("no roll number")
        return not self.errors

    def summary(self):
        return f"{self.student.name}: {len(self.errors)} problem(s)"


class ExamForm(Form):
    def __init__(self, student, papers):
        super().__init__(student)
        self.papers = papers

    def validate(self):
        ok = super().validate()
        for code in self.papers:
            if not Catalogue.exists(code):
                self.errors.append(f"unknown paper {code}")
        return ok and not self.errors

    def backlog_count(self):
        return sum(1 for code in self.papers if code.startswith("B"))

    def fee(self, days_late):
        return FeeRule.total(days_late, self.backlog_count(), self.student.concession)

    def allot_seat(self, centre, seat):
        self.centre, self.seat = centre, seat

    def seat_label(self):
        return f"{self.centre}-{self.seat}"


class BacklogForm(ExamForm):
    def validate(self):
        return super().validate() and self.backlog_count() > 0


class ContactForm(Form):
    def __init__(self, student, phone):
        super().__init__(student)
        self.phone = phone

    def validate(self):
        if len(self.phone) != 10:
            self.errors.append("phone number must have 10 digits")
        return super().validate()


class Catalogue:
    PAPERS = {"USCS501", "USCS502", "BUSCS401"}

    @staticmethod
    def exists(code):
        return code in Catalogue.PAPERS


class FeeRule:
    @staticmethod
    def total(days_late, backlog_papers, concession):
        late = 0 if days_late == 0 else 100 if days_late <= 7 else 500
        return (0 if concession else 800) + 150 * backlog_papers + late

The paper defines its metrics for any object-oriented language, and applying them to Python needs a few counting rules, which the program states in its comments: DIT counts from ExamReg's own root class (every Python class ultimately inherits from object, which would add the same 1 to every class); CBO counts the classes named inside a class's methods, in either direction, and leaves inheritance to DIT and NOC; RFC counts calls written as self.m(), super().m() or Class.m(), not calls on lists and strings; and WMC counts each method as 1. The program checks its LCOM against the paper's own example before measuring anything.

import ast
from itertools import combinations

def lcom(ivar_sets):
    """Chidamber and Kemerer's LCOM: pairs of methods sharing no instance variable (P)
    minus pairs sharing one (Q), or 0 if that is negative."""
    if not any(ivar_sets):
        return 0
    p = sum(1 for a, b in combinations(ivar_sets, 2) if not a & b)
    q = sum(1 for a, b in combinations(ivar_sets, 2) if a & b)
    return max(p - q, 0)

print("the paper's own example, {a,b,c,d,e} {a,b,e} {x,y,z}: LCOM =",
      lcom([set("abcde"), set("abe"), set("xyz")]))

tree = ast.parse(open("examreg_forms.py").read())
classes = {c.name: c for c in tree.body if isinstance(c, ast.ClassDef)}
parent = {name: next((b.id for b in c.bases if b.id in classes), None) for name, c in classes.items()}
methods = {name: [f for f in c.body if isinstance(f, ast.FunctionDef)] for name, c in classes.items()}

def ancestry(name):                          # the class, then its parent, then its parent ...
    while name:
        yield name
        name = parent[name]

def is_self_attribute(node):
    return isinstance(node, ast.Attribute) and isinstance(node.value, ast.Name) and node.value.id == "self"

def instance_variables(name):
    """Every self.x assigned in the class or in one of its ancestors."""
    found = set()
    for c in ancestry(name):
        for n in ast.walk(classes[c]):
            for target in getattr(n, "targets", []) + [getattr(n, "target", None)]:
                for t in (target.elts if isinstance(target, ast.Tuple) else [target]):
                    if is_self_attribute(t):
                        found.add(t.attr)
    return found

def response_set(name):
    """The class's own methods, plus every method they call as self.m(), super().m() or Class.m()."""
    def where(cls, method):                  # the class in which a called method is defined
        return next(c for c in ancestry(cls) if method in {f.name for f in methods[c]})
    rs = {f"{name}.{f.name}" for f in methods[name]}
    for f in methods[name]:
        for call in ast.walk(f):
            if not (isinstance(call, ast.Call) and isinstance(call.func, ast.Attribute)):
                continue
            target, method = call.func.value, call.func.attr
            if isinstance(target, ast.Name) and target.id == "self":
                rs.add(f"{where(name, method)}.{method}")
            elif isinstance(target, ast.Call) and getattr(target.func, "id", "") == "super":
                rs.add(f"{where(parent[name], method)}.{method}")
            elif isinstance(target, ast.Name) and target.id in classes:
                rs.add(f"{target.id}.{method}")
    return rs

# classes named inside a class's methods (inheritance is measured by DIT and NOC, not counted again)
named = {name: {n.id for f in methods[name] for n in ast.walk(f) if isinstance(n, ast.Name)}
               & (classes.keys() - {name}) for name in classes}

print(f"{'class':<12}{'WMC':>5}{'DIT':>5}{'NOC':>5}{'CBO':>5}{'RFC':>5}{'LCOM':>6}")
for name in classes:
    ivars = instance_variables(name)
    used = [{n.attr for n in ast.walk(f) if is_self_attribute(n) and n.attr in ivars} for f in methods[name]]
    wmc = len(methods[name])                 # every method's complexity taken as 1
    dit = len(list(ancestry(name))) - 1
    noc = sum(1 for c in classes if parent[c] == name)
    cbo = sum(1 for other in classes if other != name and (other in named[name] or name in named[other]))
    print(f"{name:<12}{wmc:>5}{dit:>5}{noc:>5}{cbo:>5}{len(response_set(name)):>5}{lcom(used):>6}")

the paper's own example, {a,b,c,d,e} {a,b,e} {x,y,z}: LCOM = 1
class         WMC  DIT  NOC  CBO  RFC  LCOM
Form            3    0    2    0    3     0
ExamForm        6    1    1    2   10     7
BacklogForm     1    2    0    0    3     0
ContactForm     2    1    0    0    4     0
Catalogue       1    0    0    1    1     0
FeeRule         1    0    0    1    1     0

The first line proves the LCOM function agrees with the paper. Then the table, read as a reviewer and a tester would read it:

• ExamForm stands out on every column that matters. It has the most methods (WMC 6), is coupled to both helpers (CBO 2), and a message to it can set ten different methods running (RFC 10). By the paper's viewpoints it will take the most effort to maintain and the most care to test.
• Its LCOM of 7 is a design finding. Of its six methods, four work on the papers, the errors and the student; two, allot_seat and seat_label, work only on the centre and the seat, and share nothing with the rest. Fifteen pairs of methods, eleven sharing nothing, four sharing something: 11 - 4 = 7. Allotting a seat is a different responsibility from checking an exam form, and the metric suggests what a reviewer would: move it to a class of its own, a SeatAllotment.
• Form's NOC of 2 is a testing finding. Two classes inherit its validate, and both call it through super(); a defect in it breaks all three forms.
• BacklogForm's DIT of 2 is the deepest: to know what its validate does, a reader must read three classes. Its RFC of 3 is small, but two of the three methods it can run belong to its ancestors.
• Form's LCOM of 0 and ContactForm's of 0 say those classes hang together: every pair of methods shares an instance variable.

Using the suite

The metrics are useful as a way of choosing where to look, not as scores. A tester reads them to direct effort: classes with high RFC and CBO need the most integration testing and the most careful test doubles (Chapter Thirty-Four, on unit testing techniques); classes with high NOC need their inherited methods tested in every subclass that uses them. A reviewer reads them to question the design: a high LCOM asks whether the class should be split, and a high CBO whether the classes should know so much about each other.

Two cautions come from the paper itself. WMC's complexity weighting is "left as an implementation decision", so two tools' WMC values are comparable only with the same weighting. And an LCOM of 0 "does not imply maximal cohesiveness, since within the set of classes with LCOM = 0, some may be more cohesive than others." Every value, as Chapter Sixty-Five insisted of every metric, means something only with its counting rule, which is why this chapter states its own.

What it does not mean

A high value is not a defect. It is a reason to look: a large class may be large for good reasons.

Deeper inheritance is not simply worse. The paper gives both sides: harder to predict, but more reuse.

LCOM 0 is not perfect cohesion. It means the sharing pairs are at least as many as the disjoint ones.

The suite does not replace testing. It points testing at the classes where defects are most likely to be expensive.

Quick revision

• CK suite (Chidamber and Kemerer, IEEE TSE 1994): six metrics for object-oriented design, measured per class.
• WMC: sum of method complexities; with complexities of 1, the number of methods.
• DIT: depth in the inheritance tree; NOC: number of immediate subclasses.
• CBO: number of other classes coupled to it (one uses the other's methods or instance variables).
• RFC: size of the response set, the class's methods plus the methods they call (first level).
• LCOM: disjoint method pairs minus sharing pairs, or 0; the paper's example gives 1.
• Worked example: ExamForm WMC 6, CBO 2, RFC 10, LCOM 7 (11 disjoint pairs, 4 sharing): split out seat allotment; Form NOC 2; BacklogForm DIT 2.
• Use: to direct testing and review effort; state the counting rules.

Test yourself

1. Name and define the six CK metrics. WMC, the sum of the complexities of a class's methods (the number of methods if each counts 1); DIT, the depth of the class in the inheritance tree; NOC, the number of its immediate subclasses; CBO, the number of other classes it is coupled to; RFC, the number of methods that can be executed in response to a message to it, its own methods plus those they call; LCOM, the number of pairs of its methods sharing no instance variable minus the number sharing one, or zero.

2. Compute LCOM for a class whose three methods use the instance variables {a, b}, {b, c} and {d}. Pairs: the first two share b (one sharing pair); the first and third, and the second and third, share nothing (two disjoint pairs). LCOM = 2 - 1 = 1.

3. What do high values of CBO and RFC mean for a tester? A class coupled to many others, or whose methods call many methods, is harder to test and debug: its behaviour depends on more code, it needs more test doubles in unit testing and more integration tests, and it deserves more of the testing time.

4. What does a high LCOM suggest, and what did it suggest in the worked example? That the class's methods fall into groups that do not share data, so the class probably has more than one responsibility and should be split. In ExamForm, two methods used only the centre and seat, so seat allotment could become a class of its own.

5. Give one advantage and one disadvantage of a deep inheritance tree, in the CK paper's terms. A class deep in the tree can reuse many inherited methods; but it inherits so much that its behaviour is harder to predict, and deeper trees mean more classes and methods are involved, so the design is more complex.

6. Why must the counting rules for CK metrics be stated? Because the paper leaves some choices open, such as the complexity weighting in WMC, and applying the metrics to a particular language needs more (whether the language's root class counts in DIT, which calls enter RFC, whether inheritance counts as coupling), so two tools can give different values for the same class.