NPathComplexity ignores multi-part boolean expressions #56

Closed
romani opened this Issue Nov 13, 2013 · 12 comments

Comments

Projects
None yet
3 participants
Owner

romani commented Nov 13, 2013 edited

Created: 2008-11-19
Creator: Christian Oetterli
SF issue: 534

The rationale of NPath says that it takes into account also multi-part boolean expressions (http://checkstyle.sourceforge.net/config_metrics.html#NPathComplexity
). This is not the case.
At least PMD reports another NPath value for the method "aMethod2()" below.

public class NPathTest {
// Both = 4
void aMethod1() {
if (true) {
}
if (true) {
}
}
// Checkstyle = 4
// PMD = 6
void aMethod2() {
if (true || true) { // multi-part bool
}
if (true) {
}
}
}

For me PMD is right as we have 6 possible ways.

We have article for NPathComplexity algorithm.

romani changed the title from NPath Check ignores multi-part boolean expressions to NPathComplexity ignores multi-part boolean expressions Feb 13, 2015

Contributor

attatrol commented Jul 28, 2015

I am on it.

Contributor

attatrol commented Jul 31, 2015

This is a method from checkstyle/Main.java


    private static int runCheckstyle(CliOptions cliOptions)
            throws CheckstyleException, UnsupportedEncodingException, FileNotFoundException {
        // setup the properties
        final Properties props =
                cliOptions.propertiesLocation != null
                        ? loadProperties(new File(cliOptions.propertiesLocation))
                        : System.getProperties();
        // create a configuration
        final Configuration config = ConfigurationLoader.loadConfiguration(
                cliOptions.configLocation, new PropertiesExpander(props));
        // create a listener for output
        final AuditListener listener = createListener(cliOptions.format, cliOptions.outputLocation);
        // create Checker object and run it
        int errorCounter = 0;
        final Checker checker = new Checker();
        try {
            final ClassLoader moduleClassLoader = Checker.class.getClassLoader();
            checker.setModuleClassLoader(moduleClassLoader);
            checker.configure(config);
            checker.addListener(listener);
            // run Checker
            errorCounter = checker.process(cliOptions.files);
        }
        finally {
            checker.destroy();
        }
        return errorCounter;
    }

pmd 5.3.2 wrongly says that its NPath complexity is 10.

This method can be reduced to its NPath equivalent:


    simpleOne() {
            bool a = true != true ? true : true;
            try {
            }
            finally {
            }
    } 
  1. The article Nejmeh, Communications of the ACM Feb 1988 pp 188-200. says that:

    The acyclic execution path complexity for the ? operator is NP(?)=NP((exprl))+NP((expr2))+NP((expr3))+2.

    where

    The acyclic execution path complexity for any logical expression is NP(expression) = number of && and I I operators in the expression.

    so it is clear that NPath complexity of ? operator in the metod has value of 2.

  2. There is no description of try-catch-finally sequence in the original paper, but its NPath complexity should have value of 5 according to pmd calculations, the fact i cannot agree.
    I think that try-finally construction in the method is linear and thus has complexity value of 1 (2, at most, if we presume that try means inherent possibility "exceptional" branch), so full complexity of the method cannot be higher than 4.

Contributor

attatrol commented Jul 31, 2015

@romani
Can you clear the rules of NPath calculation of try-catch-finally construction?
Personally to me it resembles switch operator with catch blocks as cases.

The formula i deduced is NP(T-C-F) = (NP(try-range) + S(NP(catch)))*NP(finally), where NP(finally) = NP(finally-range) or 1, if no finally block range is present, and NP(catch) = NP(catch-range) -- here is an intresting question if multicatch should be counted as catch with multiple branches with NP(catch-expr) added to its complexity

Owner

romani commented Aug 12, 2015

Sorry for delay, i am on vacation, will answer you on beginning of September

Owner

romani commented Sep 11, 2015

@attatrol ,

pmd 5.3.2 wrongly says that its NPath complexity is 10.

first of all lets not mix all problems in one issue. In scope of this issue please resolve problem that is reported in description "multi-part bool". Please move all posts of try-catch-finally to another issue.

There is no description of try-catch-finally sequence in the original paper,

yes, because paper is almost 30 years old , there was not structure like try-catch-finally at that time.

Can you clear the rules of NPath calculation of try-catch-finally construction?

I do not know for sure, I only can presume that we could convert try-catch-finally to simple form. Example:

try {
 // statements1
}
catch ( Exception1 ex1) {
 // statements2
}
catch (Exception2 ex2) {
 // statements3
}
finally {
 // statements4
}

to

// statements1
if (ex1) {
// statements2
}
else { 
   if (ex2) {
      // statements3
   }
}
// statements4 

So formula should be:
NP(T-C-F) = NP(try-range) + NP(catches) + NP(finally)
NP(catches) = S(1:N)NP(catch-range) + S(1:N)NP(catch-expr) + 1

here is an intresting question if multicatch

Example:

try {
 // statements1
}
catch ( Exception1 | Exception2 ex1) {
 // statements2
}
finally {
 // statements3
}

to

// statements1
if (ex1 || ex2) {
// statements2
}
// statements4 

So formula should be:
NP(T-C-F) = NP(try-range) + NP(catches) + NP(finally)
NP(catches) =NP((if-range))+NP((expr))+1 --- attention: it is just the same as simple NP(if)

One more example:
Example:

try {
 // statements1
}
catch ( Exception1 ex1) {
 // statements2
}
catch (Exception2 ex2) {
 // statements3
}
catch ( Exception3 | Exception4 ex1) {
 // statements4
}
finally {
 // statements5
}

to

// statements1
if (ex1) {
// statements2
}
else { 
   if (ex2) {
      // statements3
   }
   else {
        if (ex3 || ex4) {
                 // statements4
        }
   }
}
// statements5

we need to merge two formulars to one to make it general for mix of catch and multi-catch.

Owner

romani commented Nov 2, 2015

@attatrol , do you have time to finish this issue ?

Contributor

attatrol commented Nov 2, 2015

i'm going to start on weekend.

Owner

romani commented Nov 10, 2015

@attatrol , just let me know if you need any help/explanations from me , I am OK to arrange voice call to speed up process.

Contributor

attatrol commented Nov 10, 2015

@romani, i have no difficulties, i'll do this issue in 2 parts, at first i'll reach identity with pmd report (this can be easily verified), and after that i would start to implement try-catch-finally handling. The main difficulty is the lack of time, i picked too many courses for this term and have to represent my university at mathematical competitions.

Owner

romani commented Nov 10, 2015

ok, take your time.

Owner

romani commented Dec 4, 2015

@attatrol , do not hesitate to ask me assistance for this issue.

@attatrol attatrol added a commit to attatrol/checkstyle that referenced this issue Feb 14, 2016

@attatrol attatrol Issue #56: fix NPathComplexityCheck b16a5b4

@attatrol attatrol added a commit to attatrol/checkstyle that referenced this issue Feb 16, 2016

@attatrol attatrol Issue #56: fix NPathComplexityCheck ec3873b

@attatrol attatrol added a commit to attatrol/checkstyle that referenced this issue Feb 16, 2016

@attatrol attatrol Issue #56: fix NPathComplexityCheck eef20b2

@attatrol attatrol added a commit to attatrol/checkstyle that referenced this issue Feb 16, 2016

@attatrol attatrol Issue #56: fix NPathComplexityCheck fffa416

@attatrol attatrol added a commit to attatrol/checkstyle that referenced this issue Feb 16, 2016

@attatrol attatrol Issue #56: fix NPathComplexityCheck c0ce36d

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 1, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 5e146ea

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 1, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 0218514

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 1, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 609fda7

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 4, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck b1fe0f7

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 7, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck d081ca5

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 7, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 6663fc0

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 10, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck c707de5

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 10, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 6b0c771

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 10, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 4c80ccf

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 10, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 942aa12

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 11, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck f8e3f19

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 12, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 911aac3

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 13, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 8e58d70

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 14, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck b2ab21b

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 16, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 99f8bd1

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 16, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 4739aa0

kazachka was assigned by romani Feb 16, 2017

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Feb 20, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 56eb97d

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Mar 9, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck c1f7949

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Mar 10, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 2b3ba27

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Mar 10, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck d3b26b2

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Mar 12, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck e5d0bec

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Mar 29, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck c978f60

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Mar 30, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 7f2201a

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Mar 31, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 9d7bcd3

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Apr 19, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck a8e2ac4

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Apr 21, 2017

@kazachka kazachka Issue #56: fix MainTest input files 4398eeb

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Apr 22, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 5cf20ea

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Apr 22, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck d65bbf9

romani added the bug label Apr 23, 2017

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Apr 26, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck cc4abc8

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Apr 26, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 4793fef

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Apr 27, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 5b31e12

@kazachka kazachka added a commit to kazachka/checkstyle that referenced this issue Apr 28, 2017

@kazachka kazachka Issue #56: fix NPathComplexityCheck 24bc1e7

romani added this to the 7.7 milestone Apr 28, 2017

Owner

romani commented Apr 28, 2017

fix is merged.
Thanks a lot @kazachka for such huge contribution !

romani closed this Apr 28, 2017

@timurt timurt added a commit to timurt/checkstyle that referenced this issue May 6, 2017

@kazachka @timurt kazachka + timurt Issue #56: fix NPathComplexityCheck 4f53c5e

@timurt timurt added a commit to timurt/checkstyle that referenced this issue May 6, 2017

@kazachka @timurt kazachka + timurt Issue #56: fix NPathComplexityCheck 13ff3f1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment