ancestors: actually iterate over ancestors in topological order (issue5979)
This code previously used a dequeue logic, the first ancestors seen were the
first ancestors to be emitted. In branching/merging situations, it can result
in ancestors being yielded before their descendants, breaking the object
contract.
We got affected by this issue while working on the copy tracing code. At about
the same time, Axel Hecht <axel@mozilla.com> reported the issue and provided
the test case used in this changeset. Thanks Axel.
Running `hg perfancestors` does not show a significant difference between the
old and the new version.
/*
* Styles for man pages, which match with https://mercurial-scm.org/
*
* Color scheme & layout are borrowed from
* https://mercurial-scm.org/css/styles.css
*
* Some styles are from html4css1.css from Docutils, which is in the
* public domain.
*/
body {
margin: 0;
padding: 0;
font-family: sans-serif;
}
.document {
position: relative; /* be a top of absolute positioning */
margin: 1.5em 1.8em;
padding: 0;
line-height: 1.3;
}
/* layout: toc to right */
#contents {
position: absolute;
right: 0;
top: 0;
width: 26%;
}
/* layout: others to left */
h1.title, h2.subtitle, .section { width: 72%; }
.section .section { width: auto; }
table.docinfo { max-width: 72%; }
/* headings */
h1, h2, .topic-title, .admonition-title {
font-family: "MgOpen Cosmetica", "Lucida Sans Unicode", sans-serif;
font-weight: normal;
}
h1, h2, .topic-title, .admonition-title {
margin: 1em 0 0.5em;
}
h1.title { font-size: 300%; }
h2.subtitle, h1 { font-size: 200%; }
h2, .topic-title, .admonition-title { font-size: 140%; }
/* subtitle starts with lowercase in man pages, but not in HTML */
h2.subtitle:first-letter { text-transform: uppercase; }
/* override first/last margin */
.first, h1.title, h2.subtitle { margin-top: 0 !important; }
.last, .with-subtitle { margin-bottom: 0 !important; }
blockquote, pre, dd .option-list, .field-list {
margin: 0.2em 0 1em 2em;
}
kbd, tt, pre { font-family: monospace; }
dt { font-weight: bold; }
dd { margin-bottom: 0.5em; }
th, td { padding: 0.1em 0.2em; border: 0 none; }
th { font-weight: bold; text-align: left; }
a:link, a:visited { text-decoration: underline; }
a:hover, a:focus { text-decoration: none; }
a:link { color: #00b5f1; }
a:visited { color: #5c9caf; }
a:link.toc-backref, a:visited.toc-backref {
text-decoration: none;
color: inherit; /* NOTE: `inherit' is not supported by IE6 */
}
div.admonition, div.attention, div.caution,
div.danger, div.error, div.hint, div.important,
div.note, div.tip, div.warning {
border-top: 1px #ccc solid;
border-bottom: 1px #ccc solid;
padding: 0.3em 1em;
margin: 1em;
}
div.note {
border-color: #fcc200;
}
/*
* The following styles are from Docutils.
* Please refine if necessary.
*/
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important;
}
.hidden {
display: none;
}
blockquote.epigraph {
margin: 2em 5em;
}
div.abstract {
margin: 2em 5em;
}
div.dedication {
margin: 2em 5em;
text-align: center;
font-style: italic;
}
div.figure {
margin-left: 2em;
margin-right: 2em;
}
div.footer, div.header {
clear: both;
font-size: smaller;
}
div.line-block {
display: block;
margin-top: 1em;
margin-bottom: 1em;
}
div.line-block div.line-block {
margin-top: 0;
margin-bottom: 0;
margin-left: 1.5em;
}
div.sidebar {
margin: 0 0 0.5em 1em;
border: medium outset;
padding: 1em;
background-color: #ffffee;
width: 40%;
float: right;
clear: right;
}
div.sidebar p.rubric {
font-family: sans-serif;
font-size: medium;
}
div.system-messages {
margin: 5em;
}
div.system-messages h1 {
color: red;
}
div.system-message {
border: medium outset;
padding: 1em;
}
div.system-message p.system-message-title {
color: red;
font-weight: bold;
}
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em;
}
hr.docutils {
width: 75%;
}
img.align-left {
clear: left;
}
img.align-right {
clear: right;
}
ol.simple, ul.simple {
margin-bottom: 1em;
}
ol.arabic {
list-style: decimal;
}
ol.loweralpha {
list-style: lower-alpha;
}
ol.upperalpha {
list-style: upper-alpha;
}
ol.lowerroman {
list-style: lower-roman;
}
ol.upperroman {
list-style: upper-roman;
}
p.attribution {
text-align: right;
margin-left: 50%;
}
p.caption {
font-style: italic;
}
p.credits {
font-style: italic;
font-size: smaller;
}
p.label {
white-space: nowrap;
}
p.rubric {
font-weight: bold;
font-size: larger;
color: maroon;
text-align: center;
}
pre.address {
margin-bottom: 0;
margin-top: 0;
font-family: serif;
font-size: 100%;
}
pre.literal-block, pre.doctest-block {
margin-left: 2em;
margin-right: 2em;
}
span.classifier {
font-family: sans-serif;
font-style: oblique;
}
span.classifier-delimiter {
font-family: sans-serif;
font-weight: bold;
}
span.interpreted {
font-family: sans-serif;
}
span.option {
white-space: nowrap;
}
span.pre {
white-space: pre;
}
span.problematic {
color: red;
}
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80%;
}
table.citation {
border-left: solid 1px gray;
margin-left: 1px;
}
table.footnote {
border-left: solid 1px black;
margin-left: 1px;
}
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100%;
}
ul.auto-toc {
list-style-type: none;
}
div.contents.local {
-moz-column-width: 10em;
-moz-column-gap: 1em;
-webkit-column-width: 10em;
-webkit-column-gap: 1em;
}