gcc/testsuite/c-c++-common/analyzer/infinite-loop-linked-list.c

   1 /* Various correct and incorrect ways to walk a linked list, accumulating
   2    a value.  */
   3
   4 /* { dg-additional-options "-O0" } */
   5
   6 extern int maybe_useful_work ();
   7
   8 struct node
   9 {
  10   struct node *next;
  11   int val;
  12 };
  13
  14 /* Various "while" loops.  */
  15
  16 int correct_while_loop (struct node *n)
  17 {
  18   int sum = 0;
  19   while (n)
  20     {
  21       sum += n->val;
  22       n = n->next;
  23     }
  24   return sum;
  25 }
  26
  27 int while_loop_missing_next (struct node *n)
  28 {
  29   int sum = 0;
  30   while (n) /* { dg-line "while_loop_missing_next_WHILE_LINE" } */
  31     {
  32       sum += n->val; /* { dg-line "while_loop_missing_next_LOOP_BODY" } */
  33       /* We're missing: "n = n->next;", so n does not change  */
  34     }
  35   return sum;
  36
  37   /* { dg-warning "10: infinite loop" "" { target *-*-* } while_loop_missing_next_WHILE_LINE } */
  38   /* { dg-message "10: \\(2\\) when 'n' is non-NULL: always following 'true' branch\.\.\." "" { target *-*-* } while_loop_missing_next_WHILE_LINE } */
  39   /* { dg-message "\\(3\\) \.\.\.to here" "" { target *-*-* } while_loop_missing_next_LOOP_BODY } */
  40   /* { dg-message "\\(4\\) looping back\.\.\." "" { target *-*-* } while_loop_missing_next_LOOP_BODY } */
  41   /* { dg-message "\\(5\\) \.\.\.to here" "" { target *-*-* } while_loop_missing_next_WHILE_LINE } */
  42 }
  43
  44 int while_loop_missing_next_with_work (struct node *n)
  45 {
  46   int sum = 0;
  47   while (n) /* { dg-bogus "infinite loop" } */
  48     {
  49       sum += n->val;
  50       /* We're missing: "n = n->next;", so n does not change  */
  51       /* But here we do something that could be doing useful work.  */
  52       maybe_useful_work ();
  53     }
  54   return sum;
  55 }
  56
  57 /* BUG: missing: "sum += ", so sum does not change.  */
  58
  59 int while_loop_missing_add (struct node *n)
  60 {
  61   int sum = 0;
  62   while (n) /* { dg-warning "infinite loop" } */
  63     n->val;
  64   return sum;
  65 }
  66
  67 /* Various "for" loops.  */
  68
  69 int correct_for_loop (struct node *n)
  70 {
  71   int sum = 0;
  72   for (struct node *iter = n; iter; iter = iter->next)
  73     sum += n->val;
  74   return sum;
  75 }
  76
  77 int for_loop_missing_condition (struct node *n)
  78 {
  79   int sum = 0;
  80   for (struct node *iter = n; ; iter = iter->next)
  81     sum += n->val; /* { dg-warning "infinite loop" } */
  82   return sum;
  83 }
  84
  85 int for_loop_missing_next (struct node *n)
  86 {
  87   int sum = 0;
  88   for (struct node *iter = n; iter; ) /* { dg-warning "infinite loop" } */
  89     sum += n->val;
  90   return sum;
  91 }
  92
  93 /* BUG: missing: "sum += ", so sum does not change.
  94    Not an infinite loop though, as we do iterate to the
  95    end of the list.  */
  96
  97 int for_loop_missing_add (struct node *n)
  98 {
  99   int sum = 0;
 100   for (struct node *iter = n; iter; iter = iter->next)
 101     n->val; /* { dg-bogus "infinite loop" } */
 102   return sum;
 103 }
 104
 105 /* BUG: "iter->next" should be "iter = iter->next".  */
 106
 107 int for_loop_noop_next (struct node *n)
 108 {
 109   int sum = 0;
 110   for (struct node *iter = n; iter; iter->next) /* { dg-line for_loop_noop_next_FOR_LINE } */
 111     sum += n->val; /* { dg-line for_loop_noop_next_LOOP_BODY } */
 112   return sum;
 113
 114   /* { dg-warning "31: infinite loop" "" { target *-*-* } for_loop_noop_next_FOR_LINE } */
 115   /* { dg-message "31: \\(2\\) when 'iter' is non-NULL: always following 'true' branch\.\.\." "" { target *-*-* } for_loop_noop_next_FOR_LINE } */
 116   /* { dg-message "\\(3\\) \.\.\.to here" "" { target *-*-* } for_loop_noop_next_LOOP_BODY } */
 117   /* { dg-message "\\(4\\) looping back\.\.\." "" { target *-*-* } for_loop_noop_next_LOOP_BODY } */
 118   /* { dg-message "\\(5\\) \.\.\.to here" "" { target *-*-* } for_loop_noop_next_FOR_LINE } */
 119 }
 120
 121 /* BUG: "iter = n->next" should be "iter = iter->next"
 122    and so it becomes an infinite loop at the 2nd element.  */
 123
 124 int for_loop_wrong_next (struct node *n)
 125 {
 126   int sum = 0;
 127   for (struct node *iter = n; iter; iter = n->next) /* { dg-warning "infinite loop" "" { xfail *-*-* } } */
 128     /* TODO: xfail.  */
 129     sum += n->val;
 130   return sum;
 131 }