[XML-SIG] Building a DOM tree

[Mike Olson]

This is a cryptographically signed message in MIME format.

--------------msCCE8F064DFEA8A9D1DB15A01
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

4DOM went through many iterations of how to handle the garbage collection as well.
We tried the global dictionary idea.  In the end you needed to call a function
regularly to handle trees that where just left.  Then I tried a hack of python its
self that added a new core object called a DOM instance that acted like an
instance.  This was smart enough to know that its reference count included all
external reference counts, plus the number of children it had.  This worked well,
but required the user to patch python, and in general it slowed down python by
10-15% (PY_DECREF now had to check to see if the object was a DOM Instance when
checking references).  We tried using SWIG and storing the references to a childs
parents as a CPointer, but we ran into the problem of comparision, and having to
reconstruct nodes when needed  We also had a proxy implementation that ran into the
similar problems.

We came up with the general conclusion that we cannot handle every case elegantly
so we went back to the simple "ReleaseNode" function.  This will recurively "chop"
a tree so all nodes can be collected on their own.  It does require the user to
call this function, but we figured it is better to have the user know what is going
on, and when, then to all of the sudden have parent nodes dissapearing.  It also
allows us to keep a reference to a node's parent so 2 calls to getParentNode will
return the same node..

Mike


Dieter Maurer wrote:

> Andrew M. Kuchling writes:
>  > Carsten Oberscheid writes:
>  > >At 16:22 23.03.99 -0500, Andrew M. Kuchling wrote:
>  > >Assuming that each Node object can be a member only of one single DOM tree,
>  > >wouldn't it be possible to replace the _parent_relation member of the
>  > >document element by one global _parent_relation dictionary on module level?
>  > >
>  > >   xml.dom.core._parent_relation == { id(childNode): parentNode, ... }
>  >
>  >      Hmm... hmmm... no, I can't think of any reason that wouldn't
>  > work.  Nodes can only have a single parent, and you can't mix nodes
>  > from two different document trees (unless you're Fred Drake), so key
>  > collisions aren't possible.  That would mean there's a single
>  > dictionary with lots of keys, testing Python's dictionary code a bit
>  > more, but dictionaries are supposed to handle that sort of thing, so
>  > it shouldn't cause any problems.  Shouldn't cause any problems for
>  > threading, either.  Hmmm...
> Unfortunetely, it would not solve the primary problem: safe
> garbage collection of unused DOM nodes.
>
>   Suppose, you remove the last (application) reference to a
>   DOM tree. Then, this DOM tree should be garbaged collected.
>   It is not, however, because the child "c" of the root
>   has an association "id(c) : root" in the global parent_relation
>   dictionary.
>
> You still remember "WeakDict"s
> (URL:http://www.handshake.de/~dieter/pyprojects/weakdict.html)?
> They would remove problems with cycles and parent pointers.
> However, in some rare cases, the upper context of a node
> might be lost prematurely (because parent and document owner references
> are not reference counted, a reference to an internal node
> does not protect its upper context).
>
> - Dieter
>
> _______________________________________________
> XML-SIG maillist  -  XML-SIG@python.org
> http://www.python.org/mailman/listinfo/xml-sig

--
Mike Olson
Member Consultant
FourThought LLC
http://www.fourthought.com http://opentechnology.org


---

"No program is interesting in itself to a programmer. It's only interesting as long

as there are new challenges and new ideas coming up." --- Linus Torvalds


--------------msCCE8F064DFEA8A9D1DB15A01
Content-Type: application/x-pkcs7-signature; name="smime.p7s"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="smime.p7s"
Content-Description: S/MIME Cryptographic Signature

MIIKmQYJKoZIhvcNAQcCoIIKijCCCoYCAQExCzAJBgUrDgMCGgUAMAsGCSqGSIb3DQEHAaCC
CCUwggTvMIIEWKADAgECAhAOCY8cYeSQOObs5zKyDmWRMA0GCSqGSIb3DQEBBAUAMIHMMRcw
FQYDVQQKEw5WZXJpU2lnbiwgSW5jLjEfMB0GA1UECxMWVmVyaVNpZ24gVHJ1c3QgTmV0d29y
azFGMEQGA1UECxM9d3d3LnZlcmlzaWduLmNvbS9yZXBvc2l0b3J5L1JQQSBJbmNvcnAuIEJ5
IFJlZi4sTElBQi5MVEQoYyk5ODFIMEYGA1UEAxM/VmVyaVNpZ24gQ2xhc3MgMSBDQSBJbmRp
dmlkdWFsIFN1YnNjcmliZXItUGVyc29uYSBOb3QgVmFsaWRhdGVkMB4XDTk5MDMwNTAwMDAw
MFoXDTk5MDUwNDIzNTk1OVowggEKMRcwFQYDVQQKEw5WZXJpU2lnbiwgSW5jLjEfMB0GA1UE
CxMWVmVyaVNpZ24gVHJ1c3QgTmV0d29yazFGMEQGA1UECxM9d3d3LnZlcmlzaWduLmNvbS9y
ZXBvc2l0b3J5L1JQQSBJbmNvcnAuIGJ5IFJlZi4sTElBQi5MVEQoYyk5ODEeMBwGA1UECxMV
UGVyc29uYSBOb3QgVmFsaWRhdGVkMSYwJAYDVQQLEx1EaWdpdGFsIElEIENsYXNzIDEgLSBO
ZXRzY2FwZTETMBEGA1UEAxQKTWlrZSBPbHNvbjEpMCcGCSqGSIb3DQEJARYabWlrZS5vbHNv
bkBmb3VydGhvdWdodC5jb20wgZ8wDQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBANKGswZUnQ/B
IfNlZWIIy6G6AkyjYgPRhXynebPtI5ARMq9xDo2zgLgWE+8QffdoZp2hUnTpm63B6cG8yqH1
PnA/7SB2roIfml1vnOwXgNuBctciTmnrac4GWgL0CM9839fJZh47QIVYPlCbOPtnvnH1NGGD
jFWAVX7vmES72Dl9AgMBAAGjggGPMIIBizAJBgNVHRMEAjAAMIGsBgNVHSAEgaQwgaEwgZ4G
C2CGSAGG+EUBBwEBMIGOMCgGCCsGAQUFBwIBFhxodHRwczovL3d3dy52ZXJpc2lnbi5jb20v
Q1BTMGIGCCsGAQUFBwICMFYwFRYOVmVyaVNpZ24sIEluYy4wAwIBARo9VmVyaVNpZ24ncyBD
UFMgaW5jb3JwLiBieSByZWZlcmVuY2UgbGlhYi4gbHRkLiAoYyk5NyBWZXJpU2lnbjARBglg
hkgBhvhCAQEEBAMCB4AwgYYGCmCGSAGG+EUBBgMEeBZ2ZDQ2NTJiZDYzZjIwNDcwMjkyOTg3
NjNjOWQyZjI3NTA2OWM3MzU5YmVkMWIwNTlkYTc1YmM0YmM5NzAxNzQ3ZGE1ZDNmMjE0MWJl
YWRiMmJkMmU4OTIxM2FlNmFmOWRmMTE0OTk5YTNiODQ1ZjlmM2VhNDUwYzAzBgNVHR8ELDAq
MCigJqAkhiJodHRwOi8vY3JsLnZlcmlzaWduLmNvbS9jbGFzczEuY3JsMA0GCSqGSIb3DQEB
BAUAA4GBAIuxBeIOBMHbj5yM/Vu4UJxDcz4Xtc7h0K8c6d82SiwwKLN5Gbew69PevcN6Ak+p
D8LO4NyCH8Cfu3acoT0Efi99XjWvdi2eSbDJUw6MvgJtnAfY03zM+Cf31A/1iyrvr3hD45/c
yhUNRh8f6qX1NzeKvvh5AcYD1bsi+0wnP0D8MIIDLjCCApegAwIBAgIRANJ2Lo0UDD19sqgl
Xa/uDXUwDQYJKoZIhvcNAQECBQAwXzELMAkGA1UEBhMCVVMxFzAVBgNVBAoTDlZlcmlTaWdu
LCBJbmMuMTcwNQYDVQQLEy5DbGFzcyAxIFB1YmxpYyBQcmltYXJ5IENlcnRpZmljYXRpb24g
QXV0aG9yaXR5MB4XDTk4MDUxMjAwMDAwMFoXDTA4MDUxMjIzNTk1OVowgcwxFzAVBgNVBAoT
DlZlcmlTaWduLCBJbmMuMR8wHQYDVQQLExZWZXJpU2lnbiBUcnVzdCBOZXR3b3JrMUYwRAYD
VQQLEz13d3cudmVyaXNpZ24uY29tL3JlcG9zaXRvcnkvUlBBIEluY29ycC4gQnkgUmVmLixM
SUFCLkxURChjKTk4MUgwRgYDVQQDEz9WZXJpU2lnbiBDbGFzcyAxIENBIEluZGl2aWR1YWwg
U3Vic2NyaWJlci1QZXJzb25hIE5vdCBWYWxpZGF0ZWQwgZ8wDQYJKoZIhvcNAQEBBQADgY0A
MIGJAoGBALtaRIoEFrtV/QN6ii2UTxV4NrgNSrJvnFS/vOh3Kp258Gi7ldkxQXB6gUu5SBNW
LccI4YRCq8CikqtEXKpC8IIOAukv+8I7u77JJwpdtrA2QjO1blSIT4dKvxna+RXoD4e2HOPM
xpqOf2okkuP84GW6p7F+78nbN2rISsgJBuSZAgMBAAGjfDB6MBEGCWCGSAGG+EIBAQQEAwIB
BjBHBgNVHSAEQDA+MDwGC2CGSAGG+EUBBwEBMC0wKwYIKwYBBQUHAgEWH3d3dy52ZXJpc2ln
bi5jb20vcmVwb3NpdG9yeS9SUEEwDwYDVR0TBAgwBgEB/wIBADALBgNVHQ8EBAMCAQYwDQYJ
KoZIhvcNAQECBQADgYEAiLg3O93alDcAraqf4YEBcR6Sam0v9vGd08pkONwbmAwHhluFFWoP
uUmFpJXxF31ntH8tLN2aQp7DPrSOquULBt7yVir6M8e+GddTTMO9yOMXtaRJQmPswqYXD11Y
Gkk8kFxVo2UgAP0YIOVfgqaxqJLFWGrBjQM868PNBaKQrm4xggI8MIICOAIBATCB4TCBzDEX
MBUGA1UEChMOVmVyaVNpZ24sIEluYy4xHzAdBgNVBAsTFlZlcmlTaWduIFRydXN0IE5ldHdv
cmsxRjBEBgNVBAsTPXd3dy52ZXJpc2lnbi5jb20vcmVwb3NpdG9yeS9SUEEgSW5jb3JwLiBC
eSBSZWYuLExJQUIuTFREKGMpOTgxSDBGBgNVBAMTP1ZlcmlTaWduIENsYXNzIDEgQ0EgSW5k
aXZpZHVhbCBTdWJzY3JpYmVyLVBlcnNvbmEgTm90IFZhbGlkYXRlZAIQDgmPHGHkkDjm7Ocy
sg5lkTAJBgUrDgMCGgUAoIGxMBgGCSqGSIb3DQEJAzELBgkqhkiG9w0BBwEwHAYJKoZIhvcN
AQkFMQ8XDTk5MDMyOTE4MTUyNFowIwYJKoZIhvcNAQkEMRYEFBZpSOp7ojW9wE8anlR7z4lX
hS1aMFIGCSqGSIb3DQEJDzFFMEMwCgYIKoZIhvcNAwcwDgYIKoZIhvcNAwICAgCAMAcGBSsO
AwIHMA0GCCqGSIb3DQMCAgFAMA0GCCqGSIb3DQMCAgEoMA0GCSqGSIb3DQEBAQUABIGAqAhB
I4qOI4WuO42v73nUizzOKhuPW3lZLrI8rCJTb0Rw8Kg5g0VN2LbxLeofiiOQZxAhRsihccxa
ulxLtOzteUMVvIxq4Sb1aR/2YYJ0Q5JrsR/X9WQYZpShqng6LhwkxoiGr5XwgveYwg2VYyH7
TZWyb7q6VITWzmIeBHXuu7Y=
--------------msCCE8F064DFEA8A9D1DB15A01--