24861 - (nested-quotes) Quotes nesting doesn't work [GC]

Status: VERIFIED FIXED

(Core :: CSS Parsing and Computation, defect, P2)

Description

[Pierre Saslawsky]

The 'quotes' property allows you to specify the symbols you want for several 
levels of nested quoted strings. In Mozilla, the same first two symbols are used 
for all the levels of nesting.

The CSS spec is at http://www.w3.org/TR/html4/struct/text.html#edef-Q

A testcase will be attached.

Comment 1

[Pierre Saslawsky]

Attachment: testcase

Comment 2

[extremely]

Yow finally got to looking at this bug.  *sigh* While the CSS "quotes" part 
works, the FrameConstructor isn't actually tracking QuoteDepth. See:
http://lxr.mozilla.org/seamonkey/source/layout/html/style/src/nsCSSFrameConstru
ctor.cpp#725

Or look for the string:
PRUint32  quoteDepth = 0;  // XXX really track the nested quotes...

Yowch it just sets it to zero right now.  There is no place set up to track 
quotedepth or retrieve the value for these tricks.  It will always use the 
first quote set.

According to the CSS2 (which the quotes trick is from =) docs:
   http://www.w3.org/TR/REC-CSS2/generate.html#propdef-quotes
  "Note that this quoting depth is independent of the nesting of the source    
document or the formatting structure. "
That implies to me that a simple int set to zero for each page and then simply
inc'd and dec'd in the
  case eStyleContentType_OpenQuote:
  case eStyleContentType_CloseQuote:
  case eStyleContentType_NoOpenQuote:
  case eStyleContentType_NoCloseQuote:
cases would work.  It's just I dunno how to make and track that page variable
quoteDepth =)

Hopefully I at least saved somebody some searching about.

Comment 3

[Pierre Saslawsky]

Thanks much for the investigation.
I guess the quoteDepth can be tracked in the Document.

Comment 4

[Pierre Saslawsky]

With the comments above, the fix should be fairly easy.
Reassigned to attinasi to relax between more serious bugs.

Comment 5

[Marc Attinasi]

A comment from Troy:

No, you can't store it in the document, because the quote depth is presentation 
specific. It would need to be stored in the frame construction code. 

Why are you working on nested quoted? We're explicitly not supporting it for 
version 1.0. It's not that hard to get it correct during the initial creation of 
the frame model, but when the content model changes you would need to reevaluate 
the nested quotes and that is going to take some work to get it right. 

Moving target milestone off a ways...

Comment 6

[Marc Attinasi]

Marking REMIND on the advice of Troy - not going into Gecko 1

Comment 7

[Hixie (not reading bugmail)]

As per meeting with ChrisD yesterday, taking QA.

Comment 8

[Hixie (not reading bugmail)]

*** Bug 1061 has been marked as a duplicate of this bug. ***

Comment 9

[Matthew T (active 1999-2002)]

Additional testcases, with demonstrations of correct behavior:
<http://bugzilla.mozilla.org/showattachment.cgi?attach_id=4733>

Comment 10

[Marc Attinasi]

Accepting to get bugzilla off my back. Will get to this post-RTM

Comment 11

[Stephan Niemz]

*** Bug 64907 has been marked as a duplicate of this bug. ***

Comment 12

[Ulrich Drepper]

See 87497 for the previous discussion.  It was suggested to move the discussion
here.

> What's the performance impact of this [87497] patch?

I haven't done measurements but I doubt it's much.  The loop climbs up the
document tree and therefore depends on the complexity of the document.  Each
round of the loop consists of a few simply pointer comparisons.

> Does it pass the "party tricks" part of >
http://www.bath.ac.uk/~py8ieh/internet/eviltests/content/2.html ?

No.  But I'm not sure this is a problem of the part I changed.  It probably
means that the wrong style sheet rule is used.

> Does it pass an equivalent test constructed in a random order using the DOM?

Don't know, do you have an example?

As I've said before, from what I read here my interpretation of the CSS2 differs
from what people here think.  I was assuming that nesting for the same tag is
relevant and not for all uses of quotes.  Also, the class is not taken into
account to compute the nestin elvel (should it)?

It probably would be good to get some definite answers on this and also some
test case for the DOM constructed text people were worried about.

Comment 13

[Hixie (not reading bugmail)]

I'll look into making DOM tests.

Comment 14

[Hixie (not reading bugmail)]

See also the following comments from the bug I'm about to mark as a dup:

------- Additional Comments From Daniel Glazman 2001-06-29 03:17 -------

I think that your patch is incorrect. You assume that quotes are always
generated by the same tag, aren't you ?

This is false ; quotes are generated by elements that are selected by a rule 
containing a pseudo :before or :after with a 'content' declaration with
open-quote and/or close-quote values...

Hixie: yes, there is a performance hit in the proposed patch because it crowls
over all the element's ancestors each time a quote is inserted...

Comment 15

[Hixie (not reading bugmail)]

*** Bug 87497 has been marked as a duplicate of this bug. ***

Comment 16

[Ulrich Drepper]

> I think that your patch is incorrect. You assume that quotes are always
> generated by the same tag, aren't you ?

Yes, I've written this before here.  The way I've implemented it is how all
style sheets for SGML-like worked.  If the w3c's css2 defines it differently
(and the wording in the standard document is less than clear) it is invention. 
I can live with it but it should be made explicitly clear somewhere.

Comment 17

[Daniel Glazman (:glazou) (not active in Mozilla any more)]

I have a problem with this bug : I don't see, given our implementation, any
solution for an implementation not having a high performance hit nor a high
footprint impact :-(

Comment 18

[Ulrich Drepper]

> I have a problem with this bug : I don't see, given our implementation, any
> solution for an implementation not having a high performance hit nor a high
> footprint impact :-(

I completely agree.  I've looked at a similar problem

  http://bugzilla.mozilla.org/show_bug.cgi?id=35768

and added some comments there.  I think this is a more generic problem which
requires decisions to be made ASAP.  The problem in general is:

  You have a tree.  Each node has a property which can depend on the
  properties of any or all of the nodes higher up in the tree.  The
  tree can be modified by adding more nodes or removing arbitrary nodes
  anywhere.  How to effectively track the track the property value?

The simplest solution is constant recomputation.  This cost would only hit those
who use the features requiring that.  The two cases I'm concerned about both
deal with i18n and I certainly don't want to discourage anybody from making the
publications more widely usable by punishing the reader.

One alternative is to store for each of the properties to track a pointer to the
node which last modified the property.  Any such pointer will point to the
parent, the parent of the parent, ...

For the quoting level it would point the the last node using quotes.  For the
lang pseudo-class it would point to the last node with a lang attribute definition.

The problem with this is that, beside from increasing the memory usage, all
routines modifying the tree have to be taught to update these pointers.  I'm not
yet familiar enough with the source tree to say whether all this code is located
in a few places to make this job feasable.  (Anybody want to comment on this?) 
The runtime implact would also exclusively be felt in tre modification code
(DOM).  The display code would be fast.  I think this is acceptable since DOM
code shouldn't be that fequent. 

I think this is a worthwhile approach but have one problem.  The requirement of
the pointer pointing to a parent, ... would mean that this mechanism could not
be used for counters (which I think are also not implemented and which would be
next on my list of things to do).  The counters don't have to be reset over
subtree boundaries and so finding the predecessor in the tree is not that easy.
 I'm not sure what impact (if any) this will have but it's worth mentioning.


I would really like to get some feedback on this.  What is the current feeling
of sacrifizing memory and/or runtime?

Comment 19

[timeless]

it'd probably cost a lot, but i think you could have a 'list of impressionable 
children'. either (1) containing the actual affected children or their 
(2) ancestor which is a child of the given node.  The second approach should 
cost less for storage but more for traversals while checking whether a node 
cared about the impression. (A)

assuming impressionable children know what attributes matter, it could be a 
(B) hash from attribute to nodelist so that traversal/checking is only done for 
truly affected nodes. [this adds mem cost (and list navigation) and decreases 
node traversal cost]

If parents aren't told that children are no longer interested then at some point 
all nodes could include all their children (2) or descendants (1) [yuck]. O(n)

A it's probably nearly impossible to decide when to remove a node. full rebuild 
[O(n^2)?]
Removal of nodes when updating a node:
1B go through correct hash and update all nodes O(N); go to each ancestor and 
remove all nodes which you just clobbered from the correct hash.
2B go through correct hash of children *recursive* and update all nodes for 
attribute; go to the parent and remove Hash{attribute=>self} - O(1)

So basically the only idea i'm listing, that makes any sense to me is 2B, adds 
hashes to arrays of children + time to traverse each of those down to the nodes 
that really care. -- This is probably to expensive both in time and space to 
consider (although it shouldn't take any space if no nodes need this feature)

The inheritance stuff is the RTL attribute, right? 

drepper:
HTML->BODY->b->c[sets/broadcasts]{pointer to P}->d->e->P[cares/listens].
So if i set e it would have to go through its ancestors looking for affected 
children. At C how does it know that P is a descendant of e? [my guess is go to 
P and then traverse up until reaching e or c] For revevant entries, it would 
remove the pointer to P, update P and add P to it's [e] own list?

hrm, so it's like 1B. (using less space but requiring acceptable upward 
traversals

Comment 20

[Ulrich Drepper]

> HTML->BODY->b->c[sets/broadcasts]{pointer to P}->d->e->P[cares/listens].
> So if i set e it would have to go through its ancestors looking for affected 
> children. At C how does it know that P is a descendant of e? [my guess is go
> to P and then traverse up until reaching e or c] For revevant entries, it
> would remove the pointer to P, update P and add P to it's [e] own list?

I'm not sure I really understand.  You want to add forward references which let
you find children depending on the current node easily.  While this is nice
for updating this isn't what I meant.  I was only concerned about speed in
the display code.  For this backward references are needed.  In your example:

  HTML   ->   nsnull
  BODY   ->   nsnull
  b      ->   nsnull
  c      ->   nsnull   (neither of these nodes has predecessor w/ the property)
  d      ->   &c
  e      ->   &c
  P      ->   &c

What this data structure buys you is a relative easy way to find out the value
for the current node.  In case of quotes count the number of back refs != nsnull
and add one to get the local value (could optionally be stored locally).  For
the :lang() pseudo-class you can for each node find out where it was last
changed (simply follow the back ref once).

Updating this data structure is a bit more complex:

  mybackref := current back reference
  myref := reference to current, changed node
  add all children to worklist
  for each node on worklist
    if backref in node == mybackref
      change backref to myref
      add all children of this node to worklist
    remove this node from the worklist

This you would have to run whenever the property of the node we are interested
in changes.  Removing node would require a similar algorithm.  Node that the
loop terminates as soon as it finds that the backreference is not the same as
for the changed node (which means another changed node is in between). This can
be a big win.  The costs therefore are:

  for display:
     for quotes:  level stored locally: O(1)
                  traverse to root:     O(n), in a real document rather O(ln N)
     for :lang(): O(1)

  for adding/removing an important node:
                  visit all children which point to removed node
                  (for quotes with locally stored level visit all children)
                  O(n)

  for adding/removing an unimportant node:
                  O(1).  if the parent is using the property use pointer to
                  parent, otherwise use same value as pointer in parent

From my point of view this is an acceptable solution.  It's not adding much
overhead (one pointer plus a member to store the property, language or quote
nesting level) and the important operations are fast.  It's only the insert
operations which take more time.  Note that while constructing the tree from
ground up one can easily keep track of the properties in O(1).


I might be missing something fundamental.
                  

Comment 21

[Daniel Glazman (:glazou) (not active in Mozilla any more)]

Speaking of quotes implementation and language, don't forget what CSS 2 spec
says, and that adds another bit of complexity to the thing....

------------- QUOTATION BEGINS ------------- 

Note. If a quotation is in a different language than the surrounding text, it is
customary to quote the text with the quote marks of the language of the
surrounding text, not the language of the quotation itself.

Example(s):

For example, French inside English:
The device of the order of the garter is ?Honi soit qui mal y pense.? English
inside French:
Il disait: « Il faut mettre l'action en ? fast forward ?.»

A style sheet like the following will set the 'quotes' property so that
'open-quote' and 'close-quote' will work correctly on all elements. These rules
are for documents that contain only English, French, or both. One rule is needed
for every additional language. Note the use of the child combinator (">") to set
quotes on elements based on the language of the surrounding text:

[LANG|=fr] > *  { quotes: "«" "»" "\2039" "\203A" }
[LANG|=en] > *  { quotes: "\201C" "\201D" "\2018" "\2019" }

The quotation marks for English are shown here in a form that most people will
be able to type. If you can type them directly, they will look like this:

[LANG|=fr] > * { quotes: "«" "»" "?" "?" }
[LANG|=en] > * { quotes: "?" "?" "?" "?" }

------------- QUOTATION ENDS -------------

Comment 22

[Ulrich Drepper]

> Speaking of quotes implementation and language, don't forget what CSS 2 spec
> says, and that adds another bit of complexity to the thing....
> [...]

That's a different dimension (but exceptly what I meant with the reference to
:lang() in my description).  See

  http://bugzilla.mozilla.org/show_bug.cgi?id=35768

I've started looking a fixing this but it needs the same kind of decision to be
made.  The lang attribute of a node must be easily determinable.


One thing I'm not sure about (and the CSS spec doesn't say anything about) is
whether the different :lang() attributes for quotes mean different nesting
levels.  I.e., if you have

  <q lang="en">
    <q lang="fr">
      <q lang="en">

does the inner q have nesting level 2 or 3?  From your example and my
understanding it is 3.

Comment 23

[Ulrich Drepper]

Attachment: more tests with a bit of DOM as well

Comment 24

[Ulrich Drepper]

Attachment: completely new patch, tracking quotes usage

Comment 25

[Ulrich Drepper]

I've attached two more files: attachment 49626 [details] is another test which also
includes a bit of DOM code.  Nothing complicated.

The attachment 49627 [details] [diff] [review] is a new patch.  It has not much in common with the
previous patch.  It adds the capability to track the usage of quotes.  I want to
elaborate a bit how I arrived at this patch.

I was trying to locate a data structure I can directly attach the information
to.  The nsIContent data is (from my understanding) not suitable.  The quotes
handling is part of the representation which should be separated from the data
itself.

So I was looking at the nsIFrame data.  Adding the info there (even with a
single bit) seemed to be a very nice solution.  But I found the maze of frames
not suitable.  First, not all nsIContent had a frame associated.  If
no-open-quote would be used no output is generated and therefore there is no
frame.   Second, looking for quotes earlier in the hierachy seemed very tedious
at best.  It's not a simple child-parent chain to look through.  Trying to
locate the primary frame for a nsIContent failed as well since at the time
CreateGeneratedFrameFor() is called this info seems not to be available for the
newly created frame.  I tried using GetPrimaryFrameFor() and this failed.

This is how I ended up using the PresContext.  It can be used to store
representation information and what I did is adding a table which reference the
nsIContent records which are using quotes.  This way I have to walk the
nsIContent chain up to the root and count the nesting level as the number of
nsIContent record referenced in the table.

Using a (hash) table this way seems somewhat overkill.  I could add the nesting
level of each element as data to the table and avoid climbing up to the root
each time.  This would work fine without DOM but with DOM this would require a
lot of extra work since inserting would require to update the info.  I can
change this if needed but I didn't find it necessary.

The patch I append has only one problem I know of: when remoing a nsIContent
element using quotes that record must be removed from the table.  I haven't been
able to find the place where I can do this.  I'd appreciate if somebody could
point me to the place.

Comment 26

[Marc Attinasi]

nsCSSFrameConstructor::ContentRemoved could call into the PresContext to remove
the quote-content (RemoveQuoteContent). What happens then to cause all of the
frames with quotes to be reflowed and update their quote characters according to
their new nesting level?

Comment 27

[Ulrich Drepper]

> nsCSSFrameConstructor::ContentRemoved could call into the PresContext to remove
> the quote-content (RemoveQuoteContent).

I'll see whether I can figure something out.  Thanks,

> What happens then to cause all of the frames with quotes to be reflowed and
> update their quote characters according to their new nesting level?

I didn't find the reflow to be a problem.  Since this is about nesting removing
an upper-lvel quote automatically causes a reflow.  See the DOM code in the test
case I appended.  It's only the stale pointer in the hash table I have problems
with.

Comment 28

[Marc Attinasi]

> Since this is about nesting removing an upper-lvel quote automatically causes a 
> reflow. 

Oh, right, of course. I look forward to seeing your next patch!

Comment 29

[Ulrich Drepper]

Attachment: test with improved DOM part

Comment 30

[Ulrich Drepper]

Attachment: new patch with cleanup of the table after removing of content

Comment 31

[Ulrich Drepper]

I've now added some code which cleans up the hash table.  It works fine.  I just
hope it's acceptable.  The new code is invoked whenever
nsCSSFrameConstructor::ContentRemoved() is called.  It has to walk the whole tree.

I just realized that this can be optimized a bit.  I could query the number of
quote nodes stored in the table.  If it is zero there is no need to run the new
code.  If the general concept is OK I'll implement this.  The current patch is
in attachment 49727 [details] [diff] [review].  An improved test in attachment 49726 [details].  Now you can create
multiple levels of quotes and see them disappear on one button press.

Anyhow, the only remaining possible problem I can think of is with DOM genrated
CSS rules.  I'll have to read a bit about DOM to see how to write such code.

Comment 32

[Ulrich Drepper]

Attachment: optimized removing of quote refrences

Comment 33

[Ulrich Drepper]

I've attached yet another patch (attachment 49740 [details] [diff] [review]) which implements the
optimization I mentioned in the last comment.  With this optimization in place
the cleanup function isn't called if the document doesn't contain quotes.  I
found this the case most of the time when the ContentRemove function was called
which mainly happened for XUL contents.  This means that the performance
penalties are almost always near zero.

Comment 34

[Ulrich Drepper]

BTW: the document referenced the URL field

  http://www.mozilla.org/newlayout/testcases/layout/quotes.html

isn't correct, is it?  The text comes directly from HTML4 but the HTML spec
doesn't say anything about the default quotes used for "en-us".  The current
code (and I) expect the default quotes to be a single pair of ".

Maybe somebody should change the document referenced to contain

  <style type="text/css">
q { quotes: '"' '"' "'" "'" }
  </style>

Comment 35

[Hixie (not reading bugmail)]

Looks good! From looking at the patch I see two possible problems though.

The first is that it doesn't seem to handle (although I may be wrong) the case
where a single 'content' property has multiple quotes, as in:

 q:before { content: open-quote 'test' open-quote no-open-quote open-quote 'test'
                     close-quote no-close-quote; }
 q { quotes: ' <a ' ' a> ' ' <b ' ' b> ' ' <c ' ' c> ' ' <d ' ' d> ' ... ; }

The second is does this cope with siblings? As in,

   <q> Hello </q> <q> World </q>
...which should (with those CSS rules) be rendered as:

    <a test <b  <d test d> <c test <d  <f test f>

Also, how does this cope with the evil style sheet in
   http://www.bath.ac.uk/~py8ieh/internet/eviltests/content/2.html 
...? That tests most of the static aspects of this.

I have other tests here:
   http://www.hixie.ch/tests/adhoc/css/quotes/
...and here:
   http://www.hixie.ch/tests/adhoc/dom/css/quotes/I hope they help! I personally
*really* appreciate you working on this. You kick
ass! Good luck with those tests... :-D

Comment 36

[Greg K.]

Since Ulrich is working on this, shouldn't this get reassigned to him?

Comment 37

[Ulrich Drepper]

I'm not working on it at this time.  For several more weeks I have some other
high priority work to do.

Comment 38

[Boris Zbarsky [:bzbarsky]]

*** Bug 117456 has been marked as a duplicate of this bug. ***

Comment 39

[Christopher Hoess (gone)]

*** Bug 124609 has been marked as a duplicate of this bug. ***

Comment 40

[Esben Mose Hansen]

Will Ulrich Drepper be working further on this? Otherwise, I'm willing to take a
shot at the remaining issues. It'd be a real shame to lose this patch to age,
IMHO :-/

BTW: Why is it marked qawanted?!

Comment 41

[Ulrich Drepper]

"Remaining issues" is nicely phrased :-).  You have to come up with something
completely different.  The nesting level as defined in CSS2 can depend on all
the previous text and not only that which is in the text hierachy higher (which
is what my last patch did).  You'll need a data structure which allows you to
efficiently find previous places in the do which used quotes.  In addition
you'll have to be aware of the issues DOM introduces.  At any time there can be
new text inserted dynamically so you cannot associate absolute quoting nesting
levels with the places stored in the said datastructure.

Finally, the whole new concept you come up with must be general.  Counters have
very much the same problem and should be implemented in the same way.

I'd love to see this implemented since I really really want counters to be
implemented so that it us finally possible to write documents naturally in
HTML/XHTML/XML.

I've tried to get some input from various mozilla people on how this all should
be implemented but didn't get much out of them.  The problem is that this is
really a new problem.

If you want to work on it please go ahead.  If you'd discuss your plans here
first I'm willing to provide you with the bit of insight I've gained while
thinking about this.  It's not that I forgot about implementing this, I simply
don't have the time it takes in the moment.

Comment 42

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

So, many parts of the CSS2 generated content chapter were pretty poorly thought
out aren't likely to be kept in future versions of CSS (considering the
requirement for implementations to pass CR, which CSS2 never really passed, so
in some sense, it is still in CR).  Perhaps no-close-quote and no-open-quote
should be implicit rather than explicit, and quoting depth could then be
associated only with ancestor/descendant relationships and not sibling
relationships?  (Are there any existing implementations that deal with nesting
of quotes properly for unmatched pairs?  Are there any existing implementations
other than ours?)  Then perhaps the quote depth could be tracked on the style
contexts?

Perhaps the first step would be to write a more easily implementable proposal
for how this *should* work.

Comment 43

[Ulrich Drepper]

Reducing the complexity of CSS2 is certainly an option.  But you have to be
aware that this does not cause the problem to go away.  Counters, as said
before, have a very similar problem.  And if we have to support the
functionality for counters, why not as well for nesting levels?

Having said this I certainly would like to get my last patch added as a first
step.  This will cover almost 100% of the cases quotes will be used.  Not every
thinks strangely enough to come up with nesting level requirements introduced by
siblings.

And to answer your question about other implementations: I don't know about any
myself.  Just to be sure I just dowloaded amaya 6.0 which has no support. 
Neither does have opera.

Comment 44

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 49740 [details] [diff] [review]
optimized removing of quote refrences

>+NS_IMETHODIMP
>+nsPresContext::IsQuoteContent(nsIContent *aContent, PRBool &aResult)
>+{
>+  ContentHash key(aContent);
>+  return mQuoteHash.Exists(&key);
>+}

The last line here should be replaced by:

aResult = mQuoteHash.Exists(&key);
return NS_OK;

and the caller should check NS_SUCCEEDED() of the result
rather than its value directly.  Either that or you should
use |NS_IMETHOD_(PRBool)|.

Also, instead of writing ContentHash, you could use
|nsVoidKey|.


However, on a design level, I'm not sure all of this is
necessary.  The parent relationships in the style context
tree are almost identical to those in the content tree.
The nasty issue is that the :before and :after pseudo-elements
get their own style contexts as children of the element's
style context, and aren't reachable without a full search of
the style context child list (which is unordered).  This could
be handled by setting a bit on the parent style context, but
then dynamic style changes would be difficult to handle.

So it makes me somewhat uncomfortable, but perhaps the general
idea is OK.  However, why put it on the pres context?  The
relationship between nsPresContext objects and
nsCSSFrameConstructor objects is 1:1 (there is always a 1:1
pres context / pres shell relationship (and nobody can remember
why they're separate or what the distinction is, but see bug
117568), the pres shell owns the style set, and the style set
owns the frame constructor), so the quote hash could be on the
frame constructor, and we could avoid adding yet more virtual
function calls.

Comment 45

[Ulrich Drepper]

[e-mail]:

> The last line here should be replaced by: [...]

OK, makes it more consistent.

> However, on a design level, I'm not sure all of this is necessary. [...]

I don't claim to know much about the moz internals but I did tinker quite a bit
around before arriving at this design.  It was a while back but I remember to
run into problems with not seeing certain nodes if I use anything else.  I see
your point with using nsCSSFrameConstructor (you want the hash table be moved
from nsPresContext into this class?) and this could be changed.

If you have any other opinions and ideas I'd like to hear them.  Especially if
you have any ideas on how the full problem and counters can be implemented.  As
I mentioned, my main interest today are counter.  The quotes were mainly a nive
way to test the lang support I wrote (and which is already accepted).

BTW: The file I mentioned in comment #34 still isn't fixed.

Comment 46

[Boris Zbarsky [:bzbarsky]]

*** Bug 142216 has been marked as a duplicate of this bug. ***

Comment 47

[Madhur Bhatia]

This bug has been open for over 2 years now. It would be nice to have a 
foreseeable milestone set for this bug. 

Comment 48

[Esben Mose Hansen]

Attachment: A variation of 49726, this test another aspect of DOM

Comment 49

[Esben Mose Hansen]

Attachment: Another variation of 49726, this test yet another aspect of DOM

Comment 50

[Esben Mose Hansen]

Attachment: Take 1. Doesn't attempt to handle languages, but should otherwise handle all issues.

As pr. comment 41 here's my proposol for a design & implementation for this and
similar issues. 

The patch attached is a fully functional "proof of concept" patch, so if you
accept the design we already have a patch which you can pick apart :O) See
patch comments below the design comments.

Design comments:

I've attempted a "keep it simple, dammit" approach this time. 
For every Quoute and noQuote, a node is created in a doublelinked list in
nsCSSFrameConstructor. This list contains enough information to calculate the
quoting level. Furthermore, a ref to the /parent/ of the contentFrame is kept
in the list. This parent is used to keep the list sorted, lexigraphically by
position in the frame tree. 
Whenever a quote Frame is created, a node is inserted and the subsequent frames
are recalculated until the calculation match their former content. 
Whenever a quote Frame is destroyed, the node is removed from the tree.
(Actually, it's removed when it's parent frame is removed.) After all frames
that have been destroyed a removed, the List is recalculated and any changed
frames reset with the correct values.)

That's basically it. The insertion is, of course, the critical path,
performancewise. The insertion works by first checking if the node should be
appended, and if that's not the case, the insertion uses a binear search to
find the insertion point. Removal is done by simple transversal of the list.
The comparator for the frames needs to walk up the the tree, so it's O(N),
where N is depth of the tree. Thus, if M is the number of nodes in the List
Append: O(1)
Insert: O(N)*O(ln M)
Remove: O(M)
As all work is done in the frame construction, there's no rendering performance
hit.

Memorywise: A few bytes overhead, plus 32 bytes or so pr. node.

The performance hit when quotes are *not* used are construction/destruction of
one small object pr. pageload.

Patch nodes:
Almost the entire patch is in nsCSSFrameConstructor.cpp.

The QuoteList/QuoteListNode objects should maybe be split into a separate
object. nsCSSFrameConstructor.cpp is already pushing 14000 lines of code, so I
suppose added lines to this particular file is to be avoided if possible.

It would be possible to avoid roughly half the removal walkthroughs on the
QuoteList by setting a flag on nsIFrame only if the Frame is listed in the
list.

I've used the fact that child frames are always appended in
CreateGeneratedFrame(), using CreteGeneratedFrameFor(). 

The QuoteList::Destroy(nsIFrame* aFrame) is not a very good name. Suggestions
are welcome. What it does is destroying nodes with mParentFrame==aFrame.

The nodes are listed under their *parent frame*, as noQuoute's doesn't have a
Frame under which to list 'em.

Comment 51

[Esben Mose Hansen]

Hmmm. Actually it fails the "party tricks" section of Ian's evil tests. I'll
look into that. 

Also, shouldn't the default stylesheet for html contain some quotes for <Q>?

There's also an error above: Append is in O(N) time, not O(1) (unfortunately),
as one comparison is needed to estiblish if the quote should be appended.

Comment 52

[Esben Mose Hansen]

Attachment: Take 2. Corrected sign error.

The party tricks from

http://www.bath.ac.uk/~py8ieh/internet/eviltests/content/2.html

revealed a "sign error" in my patch. This should now be
corrected. However, I believe that Ian Hixie has left an exercise to the reader
in his
"evil quote test"/"party tricks" :o). I don't think the party tricks should 
display 
"Isn't it wonderful to see CSS quotes work!!!". Instead, it should
look like this:

Isn't iNO!i
NO!!wonderful to
see CS
S quotes!!!

The rest is only interesting if you would like to know why I think so.

I've added the comments in {} to Ian's source where I believe Ian's 
comments are mistaken. I've also indented Ian's code to make the
nesting easier to follow.

  <STYLE>
     /* GENERAL */
     .test { margin-left: 2em; padding: 0.1em 1em 0.1em 1em; border-left: thin
solid; }

     .ok { quotes: '"' "\""; }
     .cool { quotes: "\201C" "\201D" "\2018" "\2019"; }

     .party1 * { display: inline; }
     .party1 .a { quotes: "Isn" "'" "t" "NO!" "NO!" " i"; }
     .party1 .b { quotes: "NO!!"       "NO!!"	 
			  "wonderful " "!!!"	
			  "to "        ""   
			  "see "       " work"	  
			  "C"	       " quotes"   
			  "S"	       " "; }
     .party1 .c { quotes: none; }

     .test .no-open:before { content: no-open-quote; }
     .test .open:before { content: open-quote; }
     .test .triple-open:before { content: open-quote open-quote open-quote; }
     .test .no-close:after { content: no-close-quote; }
     .test .close:after { content: close-quote; }
     .test .triple-close:after { content: close-quote close-quote close-quote;
}

  </STYLE>

<!--					     Isn't it wonderful to see CSS
quotes work!!! 
--><div class="test c party1"><!--	     0
  --><div class="a open close"><!--	     1 Isn		       
  --></div><!-- 			     0 '		       
  --><div class="a"><!--		     0			       
    --><div class="c open"><!-- 	     1			       
      --><div class="a open"><!--	     2 t		       
      --></div><!--			     2			       
    --></div><!--			     2			       
    --><div class="no-open close"><!--	     3 [NO!]		       
    --></div><!--			     2 i		       
  --></div><!-- 			     2			       
  --><div class="close"><!--		     2			       
  --></div><!-- 			     1 t {nothing *1*}		       
    
  --><div class="a no-open no-close"><!--    2			       
    --><p class="open close"><!--	     3 {"NO!" " i" *2*} 	       
       
    --></p><!-- 			     2			       
  --></div><!-- 			     1			       
  --><div class="b no-close"><!--	     1			       
    --><hr class="no-close"><!--	     0 [NO!!]		       
    --><br class="triple-open"><!--	     3 "", "wonderful ", "to " {"NO!!"
"wonderful " "to " *3* }
    --><br class="triple-open"><!--	     6 "see ", "C", "S"  
    --><div class="open close"><!--	     7 S {* patch error*}
      --><div class="close"><!--	     7			       
	--><div class="no-close"><!--	     7			       
	  --><div class="close"><!--	     7			       
	    --><div class="no-close"><!--    7			       
	      --><div class="close"><!--     7			       
	      --></div><!--		     6			       
	    --></div><!--		     5			       
	  --></div><!-- 		     4	quotes		       
	--></div><!--			     3 [ fail to]	       
      --></div><!--			     2	work {nothing *4*}	       
    
    --></div><!--			     1 !!!		       
  --></div><!-- 			     0 [NO!!]		       
--></div><!--				     0
-->

Comments:
*1*: This DIV inherits it's quotes property from the outermost div,
which has class "c", which has quotes:none. Thus, the "t" should
not appear.

*2*: This DIV inherits it's quotes property from the immediate parent,
which has class "a". As Ian's counting suggest, this DIV should use the
3rd quote-pair, which is "NO!" "i". 

*3* The first three open quotes from class "b" are "NO!" "wonderfull"
"to", not "" "wonderful" "to".

*4* This looks like an off-by-one. The third close quote in class b is
"", not "work" (which is the 2nd pair).

Comment 53

[Esben Mose Hansen]

Marc, can I take this bug? I tried to mail you, but the mail was bounced :-(

Comment 54

[Hixie (not reading bugmail)]

D'oh! I'll look into fixing the test "soon".

Comment 55

[Esben Mose Hansen]

Thanks Ian :) Taking... this one seems a lot easier than the underline thing :-D
At least I don't have to worry about quirks...

Comment 56

[Hixie (not reading bugmail)]

Here is a version of the test that I believe is fixed:
   http://www.hixie.ch/tests/adhoc/css/quotes/002.xml
Let me know if you find any more problems...

Comment 57

[Hixie (not reading bugmail)]

FWIW there's a slightly simpler version of that test at:
   http://www.hixie.ch/tests/adhoc/css/quotes/001.xml

Comment 58

[Esben Mose Hansen]

Ok, the new testcase works when the extra »}« in line 20 is removed :O) (My
patch passes the corrected test.) 

It looks nicer with an extra space after »t« in line 8, though.

It would be just great if somebody would either comment the design or review the
patch :-D

Comment 59

[Greg K.]

Are the other, older patches attached to this bug obsolete?

Comment 60

[Ulrich Drepper]

I've marked all my patches obsolete.

Comment 61

[Ulrich Drepper]

I'm sorry to say but with the patch from attachment 88777 [details] [diff] [review] applied the test cases
don't look right.  Do I miss something?  This is on Linux (not that it should
make a difference).


One comment on the patch: we will have a very similar problem when handling
counters.  Wouldn't it be better to generate some more general data structures
which can be used for counters, too?

Comment 62

[Esben Mose Hansen]

> I'm sorry to say but with the patch from attachment 88777 [details] [diff] [review] applied the test cases
> don't look right.  Do I miss something?  This is on Linux (not that it should
> make a difference).

Could you be more explicit (where and what)? It should just work<tm>. I may have
missed something. Two things to note: Currently, the party tests have errors and
the default stylesheet has no "quotes" property, so only quotes specified on a
stylesheet shows.

> One comment on the patch: we will have a very similar problem when handling
> counters.  Wouldn't it be better to generate some more general data structures
> which can be used for counters, too?

I'm looking into counters now. The idea was to factorize the QuoteList and
QuoteListNode so that QuoteList::Next, Prev, Insert etc. was put into a common
superclass, while QuoteList::Recalc and such creatures were kept in the
QuoteList class. I believe that a new specialization of this superclass would be
able to handle counters as well, though I may be wrong. Suggestions are welcome,
though. Already, I'm discovering that tracking the counter-reset,
counter-increment poses new and challeging issues :) Also a good name for the
superclass would be welcome... I seem to have inherited Leonardo of Quirm's
namegiving ability, unfortunately.

Thanks for trying out the patch :-)

Comment 63

[Ulrich Drepper]

Well, "does not work" means it is not much (if any) improvement over the code
before.  This is the output from Hixie's code referenced in comment #57:

  Isn'tFAIL!IsnFAIL!FAIL!FAIL!FAIL!wonderful to see CSS  quotes!!!

As mentioned, I've used the patch from your "Take 2. Corrected sign error"
attachment.  Is it possible that the patch is incomplete?

Comment 64

[Esben Mose Hansen]

Attachment: Corrected test.

>Well, "does not work" means it is not much (if any) improvement over the code
>before.  This is the output from Hixie's code referenced in comment #57:

>  Isn'tFAIL!IsnFAIL!FAIL!FAIL!FAIL!wonderful to see CSS  quotes!!!

>As mentioned, I've used the patch from your "Take 2. Corrected sign error"
>attachment.  Is it possible that the patch is incomplete?

The test is broken, not the patch. I'm uploading a corrected test... (the
difference: an extra "{" has been removed and a space has been inserted to make
it look nicer.

Comment 65

[Esben Mose Hansen]

Oh, I forgot to add: You probably won't see any improvement over the previous
patch in the rendering department; the improvement is in the DOM handling, which
now works even though the affected quotes reside in another subtree in the DOM.
See the two "variations of 49726" above. Sorry I didn't make this clear before.

Comment 66

[Ulrich Drepper]

OK, an incorrect test case explains the problems.  In fact, it does now what it
is supposed to do.  Great work!


Wrt to reusing the code: what you describe is what I would have in mind myself.
 There is somewhere in moz probably some single/double linked list
implementation which you can use.  Don't ask me for names, I wouldn't know it.

Anyway, if you going to start testing some code I'm volunteering to test it. 
IMO counters are one of the most important missing features.  Which bug will you
add the patches to?

Comment 67

[Esben Mose Hansen]

> OK, an incorrect test case explains the problems.  In fact, it does now what 
> it is supposed to do.  Great work!

Thanks :-D

> Wrt to reusing the code: what you describe is what I would have in mind 
> myself.

I'll take that means you approve. Good :-) I think it's the way to go, too, and
since nobody else seems inclined to comment, I'll go ahead and do counters the
same way :o)

> There is somewhere in moz probably some single/double linked list
> implementation which you can use.  Don't ask me for names, I wouldn't know it.

PR_LIST, I believe. I already use this :-P

> Anyway, if you going to start testing some code I'm volunteering to test it. 

Thanks. I can really use that :-) 

> IMO counters are one of the most important missing features.  Which bug will 
> you add the patches to?

Bug 3247, though it may be one or two weeks before I have any patches to share
:-/ Counters are a big one (and the reason why I started patching Mozilla in the
first place... my homepage doesn't have section numbers 'cause of this bug :) ).
It may be more if anything happens in this bug or bug 1777.

Comment 68

[Hixie (not reading bugmail)]

I could not find the extraneous '}' in
   http://www.hixie.ch/tests/adhoc/css/quotes/002.xml
...mentioned in comment 58. Could you be more explicit?

Also, the space should not be necessary as it is present in the " i" close quote.

Comment 69

[Esben Mose Hansen]

I've copied and pasted the offending line below, but it wraps :-( It's quite
obvious if you just view the source in a maximized window. It the last character
on the line, beyond a lot of spaces. Perhaps searching for 20 spaces+} would
reveal it?

     .test { margin-left: 2em; }                                               
      }

As to the "t": Firstly, it *really* doesn't matter, it's pure aesthethics :-D
But the without any correction the 001.xml looks like this:

Isn't itwonderful to see CSS quotes!!!

as it should, but perhaps not as intended :o)

Comment 70

[Hixie (not reading bugmail)]

Testcases fixed, sorry about being slow. :-)

Comment 71

[Eli Friedman]

When is this patch going to be checked in?  It looks from the comments that it
works.  From what I can tell all that is needed is changes to the default
stylesheets and a multilingual solution.  Please correct me if I'm wrong.  This
could be a useful patch.

Comment 72

[Esben Mose Hansen]

The patch is awaiting reviews. I'd like a design review, but at least the
ordinary review and the superreview needs to be conducted. I requested a review
2002-7-01. If nothing happens for a while longer I'll try the next person on the
list. It's probably just the summer holidays for many people...

In particular, I would like to know whether the QuoteList class and relatives
should be put in a separate file. 

Ian's testcases works like a charm now, BTW.

P.S: Note that I made this patch as a proof-of-concept. It's just that it works
so well that I'd like to see it checked into Mozilla :-D

P.P.S: I've removed the help/qa-wanted keywords, as these make little sense now.
  The mozilla 1.1 is just plain unrealistic, now :o) The component should
probably be layout, as the style is computed find today, it's just not applied.

Comment 73

[rbs]

Some early comments:

+  /**
+    * Removes Generated content from e.g. the QuoteList.
+    */
+  NS_IMETHOD GeneratedContentFrameRemoved(nsIFrame* aFrame) = 0;
+
[...]
+
+  /*
+   * If the frame contains generated context, remove it from
+   * the quoteList
+   */
+  if (mState & NS_FRAME_GENERATED_CONTENT) {
+    nsCOMPtr<nsIStyleSet> styleSet;
+    shell->GetStyleSet(getter_AddRefs(styleSet));
+    nsCOMPtr<nsIStyleFrameConstruction> construction;
+    styleSet->GetStyleFrameConstruction(getter_AddRefs(construction));
+    construction->GeneratedContentFrameRemoved(this);
+  }

No need for these. Use [ns]QuoteList (as in Rome) and move its handling into
nsFrameManager which handles other frame-related operations. There is a readily 
available method there, NotifyDestroyingFrame(), where you can add your cleanup 
when a frame goes away.

+  mQuoteList = new QuoteList();

rather than |new|ing unconditionally, you can make the first quote trigger the 
creation.

+struct QuoteListNode : public PRCList {
+  nsStyleContentType mType;
+  nsIFrame* mParentFrame;  // Used for ordering for quotes
+  PRUint32 mQuoteDepth;    // Depth AFTER quote
+  nsIContent* mContent;    // The content where this quote resides in the DOM.
+  const nsStyleQuotes* mQuotes;

1) Add comment why it is the parent frame that is kept
2) No need to keep nsStyleQuotes, you can get it from
   mParentFrame->GetStyleData() when need arises.

In fact, I would just use a struct like this:

+struct QuoteListNode : public PRCList {
+  nsStyleContentType mType;
+  PRUint32 mQuoteDepth;
+  // the textframe that contains the quote, it is null for noQuoute
+  nsIFrame* mQuoteTextFrame;
+  // keep the parent frame because noQuoute doesn't have 
+  // a corresponding textFrame. This is used for ordering quotes. 
+  nsIFrame* mParentFrame;
+}

This will avoid using objects that are ref-counted. (Otherwise you will have to 
explain why you don't hold a ref, etc. It is simpler not to bother here since 
you can get what you want from there.)

+        mQuoteList->Insert(node);
+        PRUint32 quoteDepth = mQuoteList->Calc(node);

*If* this design is retained, merge the logic of Calc() into insert. This way, 
the depth is kept in sync as soon as the node is inserted.

+      aNode->mQuoteDepth = (node->mQuoteDepth==0) ? 0 : node->mQuoteDepth - 1;
+      return node->mQuoteDepth - 1;

beware of troubles with PRUint32.

+void QuoteList::Destroy(nsIFrame* aFrame) {

Design: it looks like your list is actually a flattened tree. Try to switch to a 
kind of "quote tree". With that, a naming can be:
+void nsQuoteTree::DeleteSubtree(nsIFrame* aFrame)

Is FrameGreater() coded efficiently -- there might be more efficient 
alternatives.

Comment 74

[Esben Mose Hansen]

> Some early comments:

Some late questions :o)

> No need for these. Use [ns]QuoteList (as in Rome) and move its handling into
> nsFrameManager which handles other frame-related operations. There is a
readily available method there, NotifyDestroyingFrame(), where you can add your
cleanup when a frame goes away.

Sound great, I'll do this shortly. 

>
> +  mQuoteList = new QuoteList();
>
> rather than |new|ing unconditionally, you can make the first quote trigger the
creation.

I suppose. Or I could just make QuoteList be a part of nsCSSFrameConstructor
object. It's only a few bytes, and quotes aren't that rare. I was newing because
I didn't wan't to mess with splitting (ns)QuoteList into a separate file, not
because it was good design. :) I went ahead and made the split. Not sure if I
should call it nsQuoteList, nsQuoteTree or nsGeneratedContent[List], though See
below.

[...]

> This will avoid using objects that are ref-counted. (Otherwise you will have
to explain why you don't hold a ref, etc. It is simpler not to bother here since
you can get what you want from there.)

Looks great. I've already made the neccessary modifications. (I still have a bit
of a hard time recognizing the refcounted objects...)
>
> +        mQuoteList->Insert(node);
> +        PRUint32 quoteDepth = mQuoteList->Calc(node);
>
> *If* this design is retained, merge the logic of Calc() into insert. This way,
the depth is kept in sync as soon as the node is inserted.

You're right I suppose. I was thinking that maybe I could make multiple
insertions, then do a final recalc when I was done. It doesn't work like that,
though, so I might as well merge them.

[...]

> beware of troubles with PRUint32.

Corrected.

>
> +void QuoteList::Destroy(nsIFrame* aFrame) {
>
> Design: it looks like your list is actually a flattened tree. Try to switch to
a kind of "quote tree". With that, a naming can be:
> +void nsQuoteTree::DeleteSubtree(nsIFrame* aFrame)

I'm not sure I understand this. Are you talking about something like this:

x --- x --- x --- x --- x
|                 |
x                 x
|
x

Where the vertical x's shared the same ParentFrame... But I can't see the
optimization (in either design or speed) so I guess I'm missing the point. Could
you please elaborate?

> Is FrameGreater() coded efficiently -- there might be more efficient alternatives.

It is coded for great efficiency, provided that I havn't missed some
information. The only information I'm using is that the frames are placed in a
tree with one common ancestor. I then determine the deepest common ancestor of
the two input frames, and determine which subtree is the former child of this
common ancestor. I don't think this can be done much better --- unless I can
somehow divine some more information... I unless I'm just missing something :o)

Thanks for your comments :-)

regards, Esben

Comment 75

[Pascal Chevrel:pascalc (PTO until April 26)]

What's the status of this bug ? it seems that a working patch is available. We
are seeing more and more nested quotes with weblogs now, it would be nice to
display nested quotes correctly for more readability. BTW, opera7b2 displays
nested quotes nicely ;-)

Comment 76

[Hixie (not reading bugmail)]

The status is that the patch needs work, I believe.

Comment 77

[Esben Mose Hansen]

To be exact: The status is that while the patch works, it is a proof-of-concept
which needs to be grafted on to mozilla much more gracefully than it is now.
I've done most of this work, I just need to figure out exactly how to do this,
from comment 73:

> No need for these. Use [ns]QuoteList (as in Rome) and move its handling into
> nsFrameManager which handles other frame-related operations. There is a
> readily available method there, NotifyDestroyingFrame(), where you can add your
> cleanup when a frame goes away.

Also, I would still like some elaboration on the "flattened" tree comment, also
from comment 73... I just don't get what you mean, sorry.

I guess I've downpriotized this with the release of CSS 2.1 which I think
removed this functionality from CSS/HTML. Maybe Mr. Hixie could tell us where
this is headed in CSS3? Are quotes gone for good, or just out for regrouping?

Comment 78

[Brian Lalonde]

CSS2.1 still includes quotes:
http://www.w3.org/TR/CSS21/generate.html#propdef-quotes

Comment 79

[Chris Applegate]

Lynx and Amaya both render one level of nested quotes (i.e. "He said, 'Bye,' and
left."). For subsequent levels of quotes, Lynx alternates between " and ', and
Amaya just uses ' for all interior quotes. Neither one, I think, supports CSS2.

The HTML spec says UAs must render nested quotes in a language-appropriate
manner, so this is at heart an HTML issue, not a CSS issue. Mozilla claims HTML
support, so it should find a decent way to handle nested quotes even
(especially) in the absence of style rules.

I humbly suggest getting Mozilla to work with at least two levels of quotes,
since few authors will nest quotes much deeper than that, and worrying about the
CSS issues when CSS2.1 is finalized or someone sees the CSS3 generated content
module working draft.

Comment 80

[Andrew Hagen]

XHTML 2.0 has the "quote" tag, which is different from the "q" tag. Bug 161463.
Not sure whether our plans for that need to mesh with this bug.

Comment 81

[Chris Applegate]

Probably not. "quote" is invisible to the user, and doesn't generate quote marks
or anything like that (unless XHTML 2.0 changes by the time it becomes a
recommendation).

Comment 82

[Hixie (not reading bugmail)]

More to the point, <quote> is expected to be styled using 'quotes' and 'content'
by the content author in CSS environments such as Mozilla. So it depends on this
bug even more than HTML's <q> element does.

Comment 83

[Brian Lalonde]

I notice that while 
 q { quotes: '"' '"' "'" "'"; }
does not work as expected,
 q { quotes: '"' '"'; }
 q q { quotes: "'" "'"; }
works just fine.

This is not only a simple workaround for site authors,
but it seems to indicate that Mozilla itself is *already* 
counting element nesting, and that the former rule could
be handled internally as the latter rules.

Am I missing something?

Comment 84

[Hixie (not reading bugmail)]

You are missing something.

It is possible to have:

   a:before { content: open-quote; }
   b:before { content: open-quote; } b:after { content: close-quote; }
   c:after { content: close-quote; }

...and have:

   <a> ... </a>
   <b> ... </b>
   <c> ... </c>

...which should have the quotes of <b> nested inside the quotes opened by <a>
and closed by <c>.

Comment 85

[Christopher Hoess (gone)]

*** Bug 213022 has been marked as a duplicate of this bug. ***

Comment 86

[Anne (:annevk)]

*** Bug 227001 has been marked as a duplicate of this bug. ***

Comment 87

[Ulrich Drepper]

Attachment: Updated patch for tree on 2003-12-30

This is an updated version of Esben's last patch.  It against the current tip
of the tree.  Compiles nicely on Linux and the smoke tests all work.  The tests
in the attachments work, too.

Additional change on top of updates:

~ the code for handling the list is in new files (.h and cpp).	None of the
functions need to be exported from the DSO/DLL.  The names are *Tree instead of
ns*List

~ the Calc function in private, it is automatically called on insert

~ the nsQuoteTreeNode structure is now as proposed in comment #73.

~ the nsQuoteTree object is now part of nsCSSFrameConstructor, not dynamically
allocated.  This increases the size of the class by only 4 bytes and the code
to handle the tree gets faster and smaller

~ the code in CreateGeneratedFrameFor got simplified.  The NoOpen/NoClose code
is not duplicated anymore.

~ I've cleaned up the code in nsFrame.cpp.  variable initialization and use are
moved closer and duplicate tests for NULL are removed

~ a few bug in the nsQuoteTree code are removed.  I've alse cleaned up that
code a bit

Of the points in comment #73 the only one not addressed is the first.  I tried
moving the code to nsFrameManager but this caused problems.  Double
free-related, probably.  I would need some pointers what is really meant here.

Comment 88

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 138187 [details] [diff] [review]
Updated patch for tree on 2003-12-30

>-  // Get the view pointer now before the frame properties disappear
>-  // when we call NotifyDestroyingFrame()
>-  nsIView* view = GetView();

...

>+  // Get the view pointer now before the frame properties disappear
>+  // when we call NotifyDestroyingFrame()
>+  nsIView* view = GetView();

This seems to be missing the point of the comment.  |GetView| won't work
anymore once |NotifyDestroyingFrame| has been called.

>+NS_IMETHODIMP 
>+nsCSSFrameConstructor::GeneratedContentFrameRemoved(nsIFrame* aFrame) {

Could you follow local bracing style?  (Function opening brace on its own
line.)

It'll take me a bit of time to look through the quote tree code -- I may not
get to it immediately.

Comment 89

[Ulrich Drepper]

Attachment: Updated patch to fix dbaron's first issues

This patch moves the GetView() call to the beginning and changes various
functions to look more like the rest of the sources.  Compiled and tested.

Comment 90

[Ulrich Drepper]

Attachment: Update for nsIStyleSet removal

bryner helped adjusting the patch for a tree without nsIStyleSet.

Comment 91

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 138591 [details] [diff] [review]
Update for nsIStyleSet removal

A few more comments, although I'm sure I'll have more (although I'm not sure
how much it's worth my looking at the current code given the first comment):

The use of |FrameGreater| seems incorrect.  It's going to fail whenever
multiple child lists are involved, and you really want content tree order
comparison anyway, not frame tree order comparison.  (I think our style tree /
frame tree relationship is backwards.)	We already have content tree order
comparison functions somewhere, but you'll probably have to be more careful
with :before vs. :after (although I haven't actually looked yet at whether you
were passing the generated content frames).

In nsCSSFrameConstructor.cpp, you changed a GetStyleQuotes call to the ugly
old-style GetStyleData call (probably bad merging).

The use of the name |QuoteTree| seems highly misleading for something that
isn't a tree.

Comment 92

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

See nsLayoutUtils::CompareTreePosition.  (However, handling :after might be tricky.)

Comment 93

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

There are also some improvements that could be made once bug 214013 lands.

Comment 94

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

nsLayoutUtils::CompareTreePosition currently does preorder comparison.  It could
be generalized quite easily (move the current function into
GeneralCompareTreePosition by adding two parameters for what to do when A is an
ancestor of B, and what to do when B is an ancestor of A).  The current function
could then call the general function with (-1, 1), a PostOrder comparison
function could pass (1, -1), and the code for this patch could call the general
code directly with (pseudo-type(A), pseudo-type(B)), where pseudo-type(:before)
is -1 and pseudo-type(:after) is 1.

Comment 95

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I also think there's a good bit of similarity between quotes and counters and
the same mechanism might be able to work for both.

Also, I'm not comfortable with the handling of dynamic changes in this patch --
destroying everything isn't a good approach, and I'm also not sure it's done
enough, although I haven't looked closely.

Comment 96

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(Or at least nsQuoteTree::Destroy should be renamed to
nsQuoteTree::DestroyNodesFor so I don't get confused about what's happening.)

Comment 97

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 138591 [details] [diff] [review]
Update for nsIStyleSet removal

>+      // Binary search.
>+      PRUint32 mask = 0x1;
>+      for (PRUint32 i = mSize; i > 1; i >>= 1) mask <<= 1;
>+      for (PRUint32 i = mSize & !mask; i>0; i--) {

I assume this is supposed to be ~ rather than !.

>+        node = Prev(node);
>+      }

Furthermore, I don't see how the code immediately following this handles size
not being a power of 2.  I'm tempted to rewrite this to avoid bit-twiddling.

Comment 98

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

This makes a bunch of untested changes to the previous patch cleaning up a
bunch of my comments.  Calc and Recalc need a bunch of work still, at a minimum
to comply with the sentence "A 'close-quote' that would make the depth negative
is in error and is ignored (at rendering time): the depth stays at 0 and no
quote mark is rendered (although the rest of the 'content' property's value is
still inserted)."  I also think it would be better if we didn't recalc the
whole quote list twice when we remove a frame that has both an opening and
closing quote -- there are a bunch of possibilities for how we could do such a
thing (events, or perhaps BeginUpdate/EndUpdate).

Comment 99

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

It would be good to see some tests of the following (both static and dynamic):
 * elements whose :before and :after don't lead to balanced quotes
 * :before and :after containing more than one of open-quote, etc. (with both
   same-side and opposite-side quotes

Comment 100

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

Better version of previous; still needs work.

Comment 101

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

This fixes the DOM issues in the previous patch, but I'm still not happy with
the dynamic change handling.

Comment 102

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

Comment 103

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

FWIW, I think Hixie's test and the corrected version above are slightly buggy. 
I don't quite pass them -- I think the "work" is in the wrong place in the
'quotes' list so it doesn't show up, and there's also a double " " where there
should only be one.

Comment 104

[Hixie (not reading bugmail)]

Tests fixed.
   http://www.hixie.ch/tests/adhoc/css/quotes/001.xml
   http://www.hixie.ch/tests/adhoc/css/quotes/002.xml

Comment 105

[Boris Zbarsky [:bzbarsky]]

I'll try to get to this asap, but it may take a week or so....

Comment 106

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 141700 [details] [diff] [review]
patch

>Index: layout/html/style/src/nsCSSFrameConstructor.cpp

> nsCSSFrameConstructor::CreateGeneratedFrameFor(nsIPresContext*       

>+        nsQuoteListNode* node =
>+          new nsQuoteListNode(type, aParentFrame, aContentIndex);

Should probably handle OOM here.

>+        // "A 'close-quote' that would make the depth negative is in
>+        // error and is ignored (at rendering time): the depth stays at

There is some very similar logic in nsQuoteList::Recalc.  I think it would make
more sense to put all this code in a method on nsQuoteListNode that can be
called from both places.... (probably a method returnin const nsAFlatString& or
something along those lines).

>Index: layout/html/style/src/nsQuoteList.cpp

>+ * Version: NPL 1.1/GPL 2.0/LGPL 2.1

This should use the MPL.

>+PRUint32
>+nsQuoteList::Calc(nsQuoteListNode* aNode)

It would be good to document what this function actually returns....  It looks
like it's returning the depth of aNode (which is the same as the depth before
aNode if aNode is opening and the depth after aNode if aNode is closing),
right?

>+void
>+nsQuoteList::Recalc(nsQuoteListNode* aNode, PRBool aContinue)

No one ever calls this with aContinue == PR_FALSE, as far as I can tell. 
Eliminate aContinue?

The code here that calculates quoteDepth is very similar to what Calc() does. 
Maybe we should factor it out?	This code also needs the same return value that
Calc() produces, I think.  The code as it is now gets prev->mQuoteDepth later
and decrementing it for close quotes, which is identical to the Calc()
algorithm, except Calc() gets the case of the node being mFirstNode right while
the code here ends up getting the quote depth off of prev even for mFirstNode,
which looks wrong to me.

So in fact, is there any reason not to make the following changes?

1)  Make this code stash away node->mQuoteDepth and then just call Calc()
2)  If the value of mQuoteDepth after Calc() is different from the value we
    stashed, then do the update
3)  Give Calc() an optional "prevNode" arg that we would pass here (Calc()
would
    just call Prev() when the arg is null).

>+#ifdef NS_DEBUG

#ifdef DEBUG, right?

>+nsQuoteList::PrintChain()

This method is never called.. I guess it's OK to leave it here for debugging
purposes, though....

>+nsQuoteList::~nsQuoteList()
>+{
>+  //Delete entire list
>+  if (!mFirstNode)
>+    return;
>+  for (nsQuoteListNode* node = Next(mFirstNode); node != mFirstNode;
>+       Next(mFirstNode))

So... node == mFirstNode is never true in this loop, right?  When do we delete
mFirstNode?  Also, that last clause of the for should probably be 

  node = Next(mFirstNode)

or something along those lines?

>+nsQuoteList::Insert(nsQuoteListNode* aNode)

>+      PR_INSERT_BEFORE(aNode, curNode);

if curNode == mFirstNode here, then we need to set mFirstNode = aNode, right?

>Index: layout/html/style/src/nsQuoteList.h

>+ * Version: NPL 1.1/GPL 2.0/LGPL 2.1

MPL, please.

>+  nsQuoteListNode(nsStyleContentType& aType, nsIFrame* aPseudoFrame,

This should probably assert a few things in the body:

1)  mType is a quotes-related type (open, noopen, close, noclose)
2)  mPseudoFrame is non-null
3)  mPseudoFrame has the NS_FRAME_GENERATED_CONTENT state flag set

>+  PRUint32 Calc(nsQuoteListNode* aNode);
>+  void Recalc(nsQuoteListNode* aNode, PRBool aContinue);

Some documentation of what these functions do would be nice (in particular what
it is Calc() returns, like I said above).


>+  void RecalcChain(nsQuoteListNode* aNode) { Recalc(aNode, PR_FALSE); }

This seems to be unused.  Is it needed?

Comment 107

[Boris Zbarsky [:bzbarsky]]

To clarify:

> >+      PR_INSERT_BEFORE(aNode, curNode);
> if curNode == mFirstNode here, then we need to set mFirstNode = aNode, right?

This is at the end of the binary search, not when appending.

Also, it would be good to include Esben's email with his name in the license
comments.

Comment 108

[Boris Zbarsky [:bzbarsky]]

One other thing.  With the batching in that patch, we avoid having to recalc the
whole list every time we remove a frame on teardown, but we _do_ have to walk
the list each time to remove every frame.  So teardown is O(N^2) in the length
of the list.  I would think that we want to just call Clear() or something on
the list at teardown, walk it once destroying all the nodes, _then_ start
tearing down the frame tree.

Comment 109

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Taking bug.

Comment 110

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I'm trying to clean up the calculation code so it doesn't have to go in multiple
places, and I'm probably going to change the mQuoteDepth to store the depth
*before* the node, so that it's easier to implement:

  A 'close-quote' that would make the depth negative is in error and is
  ignored (at rendering time): the depth stays at 0 and no quote mark is
  rendered (although the rest of the 'content' property's value is still
  inserted).

Comment 111

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

This refactors the calculation stuff a good bit, and I think it addresses all
of bz's comments, but I'll double-check that it actually does so later.

Comment 112

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

This does address all of bz's comments.  I haven't yet tested it in a debug
build to make sure all of the assertions compile and are the right way around,
but if there's a problem I expect only minor changes.

Comment 113

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I'll attach a patch that fixes a few compilation problems with the assertions. 
None of the testcases hit any of my assertions, although a few of them (such as
http://www.hixie.ch/tests/adhoc/css/quotes/001.xml ) trigger:

###!!! ASSERTION: forget-word-frame: '(void*)aFrame == mWordFrames.PeekFront()',
file /builds/quotes/mozilla/layout/html/base/src/nsLineLayout.cpp, line 3097
Break: at file /builds/quotes/mozilla/layout/html/base/src/nsLineLayout.cpp,
line 3097

Comment 114

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

Comment 115

[Boris Zbarsky [:bzbarsky]]

I'll try to look later tonight or tomorrow.

Comment 116

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 145731 [details] [diff] [review]
patch

>Index: layout/html/style/src/nsQuoteList.h

>+  // Quote depth this quote, which is always non-negative.

"before this quote", perhaps?

Why is this public if we have DepthBefore() (should we maybe make it protected
and add SetDepthBefore()?  Or just remove DepthBefore()?)

>+  void Calc(nsQuoteListNode* aNode);

Would still be nice to have a comment here explaining what that's supposed to
calculate....

r+sr=bzbarsky with those nits.

Comment 117

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Fix checked in to trunk, 2004-04-12 14:52/53 -0700.

Comment 118

[Rick Bull]

Attachment: Missing quote-marks test case

Sorry if this has been reported, but I notice that quote-marks are now missing
in HTML documents that don't have the CSS quotes property set for <Q> elements.
I assume this is probably just a regression because a Mozilla .css file needs
to be updated to include the quotes attribute. Thought I better mention it in
case nobody has noticed this yet.

Comment 119

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch ua.css (checked in to trunk, 2004-04-14 13:13 -0700)

Comment 120

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 146116 [details] [diff] [review]
patch ua.css (checked in to trunk, 2004-04-14 13:13 -0700)

This gives nice en-US defaults but doesn't prevents authors from giving better
defaults.

Comment 121

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 146116 [details] [diff] [review]
patch ua.css (checked in to trunk, 2004-04-14 13:13 -0700)

Yeah, that looks good.	r+sr=bzbarsky.	Perhaps we should look into fixing bug
16206 too, now that we can.

Comment 122

[Bill Mason]

*** Bug 268467 has been marked as a duplicate of this bug. ***

Comment 123

[Michael Stadlbauer]

*** Bug 265681 has been marked as a duplicate of this bug. ***

Comment 124

[Phil Ringnalda (:philor)]

*** Bug 271282 has been marked as a duplicate of this bug. ***

Comment 125

[Peter van der Woude [:Peter6]]

*** Bug 290495 has been marked as a duplicate of this bug. ***

Comment 126

[:Gavin Sharp [email: [e-mail]]]

*** Bug 304762 has been marked as a duplicate of this bug. ***

Comment 127

[Robert Poole]

Has there been any movement on this bug since April of last year?  It's claimed 
to be Resolved Fixed, yet end users are not seeing the fixed behavior in public 
builds of Mozilla or Firefox.  I had reported this behavior as bug 304762 just 
recently, and it was marked duplicate of this one.  (I honestly did search the 
bugs DB, but I guess I didn't type in the magic keywords.)  Regardless, if this 
issue is resolved, why are current builds of Firefox still exhibiting the wrong 
behavior?

Comment 128

[Boris Zbarsky [:bzbarsky]]

Robert, the bug has been fixed since April of last year.  You reported your bug
using Firefox 1.0.6, which is using a 1.7 stable branch build of the layout
engine.  That's layout engine code from April 1 of last year or so.

We've shipped a number of public alpha and beta builds of Mozilla and Firefox
that contain this fix (Mozilla 1.8 alphas 1, 2, and 3 come to mind, as well as
the Deer Park Alpha 1 and 2 builds of Firefox).  If you want to test layout
issues, please test in those builds, not in the very obsolete Firefox 1.0.x and
Mozilla 1.7.x builds.