5 ms·

I use assertions to protect against things like this. I liberally sprinkle my code with assertions (CS theory calls them pre-conditions and post-conditions, ii

I use assertions to protect against things like this. I liberally sprinkle my code with assertions (CS theory calls them pre-conditions and post-conditions, iirc) to crash early if the system is an invalid state. One my pet peeves is that few programmers seem to love assertions like I do. Would love to see to comments on this.

swah 14y ago
The kind of assertion he needed though, could only be ensured by the database, not application code (my impression).
- luser001 14y ago
  Agreed, infinite loops are a little hard to protect using asserts. When I hit the first infinite loop bug on a code path, I frequently add code to assert that the number of calls is less than $A_LARGE_NUMBER to catch future occurrences of the same root cause.
  - badgar 14y ago
    > Agreed, infinite loops are a little hard to protect using asserts. assert(is_tree(comment_graph)) Typically, a composite entity (like an "item" on HN which has many "comments") will define invariants to ensure data integrity. In this case, the invariant is that an "item"'s comments form a tree. The database layer often contains this logic, but it depends on how you're building your application; NoSQL backends for example typically must put validation in the application layer. Since HN just uses files, a well-developed application layer should be riddled with invariants like this.
  - mpweiher 14y ago
    I dimly remember a language that just hard-limited loops. I thought it was John Pane's HANDS system, but I can't seem to find a reference in the thesis...can anybody refresh my memory? http://www.cs.cmu.edu/~pane/research.html http://www.cs.cmu.edu/~pane/research.html http://www.cs.cmu.edu/~pane/thesis/ http://www.cs.cmu.edu/~pane/thesis/ Pretty cool work regardless, I really like the way it deals with aggregates, for example.
  - swah 14y ago
    This is similar to the "while with timeout" that is common in embedded code (of course, watchdogs are better...)
- irahul 14y ago
  The kind of assertion he needed could not be ensured by the database. The kind of assertion he needed was there are no cycles in the graph. How would you ensure that in a database? Also, HN uses flat files, not database.
  - swah 14y ago
    I was thinking something like (supposing the comments were stored as "closure tables" like Karwin suggests): CREATE TABLE comment_tree ( ascestor_id REFERENCES comments(id) NOT NULL, descendant_id REFERENCES comments(id) NOT NULL, CHECK ( ascestor_id <> descendant_id ) ) but I'm probably overlooking something. (I'm aware that HN uses flat files, I was just making a counter-point to the "simple assert" solution...)
    - irahul 14y ago
      That will prevent a child being its own parent. It won't work for more than one level i.e a post being its own grandchild. Assume (post_id, parent_id) sequence: (1, 3) -> (2, 1) -> (3, 2).
      - zzzeek 14y ago
        you can assert that "post_id > parent_id", assuming comments are always created subsequent to the creation of their parents (as is the case here) and that integer identifiers are always increasing (otherwise use timestamps). (1, 3) above would indicate an invalid case (not necessarily a cycle, but a precondition for one).
      - swah 14y ago
        Please note that the "Closure Table solution involves storing all paths through the tree, not just those with a direct parent-child relationship."
        irahul 14y ago
        My bad. I was speed reading, and didn't read the "Closure Table" part.
timothya 14y ago
What assertion would you have used in this case? For every comment you'd have to iterate through all it's parents to check if there is a cycle, which seems pretty inefficient to do for something that should never happen (there are other ways that you could check for this problem as you go, but the only other ways that I can think of require holding extra state just in order to perform the assertion). I'm for assertions when they are simple and don't cost much (especially during development), but it's not feasible to check every condition that should not happen.
- petercooper 14y ago
  You could assert a limit on depth, perhaps. Then the cycle would still exist but after X number of comments, the rendering ends.
  - timothya 14y ago
    This is a reasonable solution. While it will (almost) never provide the correct result (it might print out a cycle of comments until X is reached, or it might cut off a very long but legitimate comment thread), it would provide a reasonable guarantee on this sort of problem not generating infinite pages.
    - petercooper 14y ago
      At the risk of being accused of flame-baiting, I'd say it's the engineering solution rather than the mathematical one.. ;-) For some reason I tend to be a fan of the "stick it in a secure box" rather than "get it right in the first place" approach..
- badgar 14y ago
  >iterate through all it's parents to check if there is a cycle,which seems pretty inefficient to do for something that should never happen The number of parents is almost always under 3 or 4 and never over 100. Writes occur a few times a second at peak. You are prematurely optimizing.
- 14y ago

swah 14y ago

The kind of assertion he needed though, could only be ensured by the database, not application code (my impression).

luser001 14y ago
Agreed, infinite loops are a little hard to protect using asserts. When I hit the first infinite loop bug on a code path, I frequently add code to assert that the number of calls is less than $A_LARGE_NUMBER to catch future occurrences of the same root cause.
- badgar 14y ago
  > Agreed, infinite loops are a little hard to protect using asserts. assert(is_tree(comment_graph)) Typically, a composite entity (like an "item" on HN which has many "comments") will define invariants to ensure data integrity. In this case, the invariant is that an "item"'s comments form a tree. The database layer often contains this logic, but it depends on how you're building your application; NoSQL backends for example typically must put validation in the application layer. Since HN just uses files, a well-developed application layer should be riddled with invariants like this.
- mpweiher 14y ago
  I dimly remember a language that just hard-limited loops. I thought it was John Pane's HANDS system, but I can't seem to find a reference in the thesis...can anybody refresh my memory? http://www.cs.cmu.edu/~pane/research.html http://www.cs.cmu.edu/~pane/research.html http://www.cs.cmu.edu/~pane/thesis/ http://www.cs.cmu.edu/~pane/thesis/ Pretty cool work regardless, I really like the way it deals with aggregates, for example.
- swah 14y ago
  This is similar to the "while with timeout" that is common in embedded code (of course, watchdogs are better...)
irahul 14y ago
The kind of assertion he needed could not be ensured by the database. The kind of assertion he needed was there are no cycles in the graph. How would you ensure that in a database? Also, HN uses flat files, not database.
- swah 14y ago
  I was thinking something like (supposing the comments were stored as "closure tables" like Karwin suggests): CREATE TABLE comment_tree ( ascestor_id REFERENCES comments(id) NOT NULL, descendant_id REFERENCES comments(id) NOT NULL, CHECK ( ascestor_id <> descendant_id ) ) but I'm probably overlooking something. (I'm aware that HN uses flat files, I was just making a counter-point to the "simple assert" solution...)
  - irahul 14y ago
    That will prevent a child being its own parent. It won't work for more than one level i.e a post being its own grandchild. Assume (post_id, parent_id) sequence: (1, 3) -> (2, 1) -> (3, 2).
    - zzzeek 14y ago
      you can assert that "post_id > parent_id", assuming comments are always created subsequent to the creation of their parents (as is the case here) and that integer identifiers are always increasing (otherwise use timestamps). (1, 3) above would indicate an invalid case (not necessarily a cycle, but a precondition for one).
    - swah 14y ago
      Please note that the "Closure Table solution involves storing all paths through the tree, not just those with a direct parent-child relationship."
      - irahul 14y ago
        My bad. I was speed reading, and didn't read the "Closure Table" part.

timothya 14y ago

What assertion would you have used in this case? For every comment you'd have to iterate through all it's parents to check if there is a cycle, which seems pretty inefficient to do for something that should never happen (there are other ways that you could check for this problem as you go, but the only other ways that I can think of require holding extra state just in order to perform the assertion). I'm for assertions when they are simple and don't cost much (especially during development), but it's not feasible to check every condition that should not happen.

petercooper 14y ago
You could assert a limit on depth, perhaps. Then the cycle would still exist but after X number of comments, the rendering ends.
- timothya 14y ago
  This is a reasonable solution. While it will (almost) never provide the correct result (it might print out a cycle of comments until X is reached, or it might cut off a very long but legitimate comment thread), it would provide a reasonable guarantee on this sort of problem not generating infinite pages.
  - petercooper 14y ago
    At the risk of being accused of flame-baiting, I'd say it's the engineering solution rather than the mathematical one.. ;-) For some reason I tend to be a fan of the "stick it in a secure box" rather than "get it right in the first place" approach..
badgar 14y ago
>iterate through all it's parents to check if there is a cycle,which seems pretty inefficient to do for something that should never happen The number of parents is almost always under 3 or 4 and never over 100. Writes occur a few times a second at peak. You are prematurely optimizing.
14y ago