This file is indexed.

/usr/share/pyshared/epydoc/apidoc.py is in python-epydoc 3.0.1+dfsg-4.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

   1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113
 114
 115
 116
 117
 118
 119
 120
 121
 122
 123
 124
 125
 126
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146
 147
 148
 149
 150
 151
 152
 153
 154
 155
 156
 157
 158
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246
 247
 248
 249
 250
 251
 252
 253
 254
 255
 256
 257
 258
 259
 260
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286
 287
 288
 289
 290
 291
 292
 293
 294
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
# epydoc -- API Documentation Classes
#
# Copyright (C) 2005 Edward Loper
# Author: Edward Loper <edloper@loper.org>
# URL: <http://epydoc.sf.net>
#
# $Id: apidoc.py 1675 2008-01-29 17:12:56Z edloper $

"""
Classes for encoding API documentation about Python programs.
These classes are used as a common representation for combining
information derived from introspection and from parsing.

The API documentation for a Python program is encoded using a graph of
L{APIDoc} objects, each of which encodes information about a single
Python variable or value.  C{APIDoc} has two direct subclasses:
L{VariableDoc}, for documenting variables; and L{ValueDoc}, for
documenting values.  The C{ValueDoc} class is subclassed further, to
define the different pieces of information that should be recorded
about each value type:

G{classtree: APIDoc}

The distinction between variables and values is intentionally made
explicit.  This allows us to distinguish information about a variable
itself (such as whether it should be considered 'public' in its
containing namespace) from information about the value it contains
(such as what type the value has).  This distinction is also important
because several variables can contain the same value: each variable
should be described by a separate C{VariableDoc}; but we only need one
C{ValueDoc}, since they share a single value.

@todo: Add a cache to canonical name lookup?
"""
__docformat__ = 'epytext en'

######################################################################
## Imports
######################################################################

import types, re, os.path, pickle
from epydoc import log
import epydoc
import __builtin__
from epydoc.compat import * # Backwards compatibility
from epydoc.util import decode_with_backslashreplace, py_src_filename
import epydoc.markup.pyval_repr

######################################################################
# Dotted Names
######################################################################

class DottedName:
    """
    A sequence of identifiers, separated by periods, used to name a
    Python variable, value, or argument.  The identifiers that make up
    a dotted name can be accessed using the indexing operator:

        >>> name = DottedName('epydoc', 'api_doc', 'DottedName')
        >>> print name
        epydoc.apidoc.DottedName
        >>> name[1]
        'api_doc'
    """
    UNREACHABLE = "??"
    _IDENTIFIER_RE = re.compile("""(?x)
        (%s |             # UNREACHABLE marker, or..
         (script-)?       #   Prefix: script (not a module)
         \w+              #   Identifier (yes, identifiers starting with a
                          #   digit are allowed. See SF bug #1649347)
         '?)              #   Suffix: submodule that is shadowed by a var
        (-\d+)?           # Suffix: unreachable vals with the same name
        $"""
        % re.escape(UNREACHABLE))

    class InvalidDottedName(ValueError):
        """
        An exception raised by the DottedName constructor when one of
        its arguments is not a valid dotted name.
        """

    _ok_identifiers = set()
    """A cache of identifier strings that have been checked against
    _IDENTIFIER_RE and found to be acceptable."""
    
    def __init__(self, *pieces, **options):
        """
        Construct a new dotted name from the given sequence of pieces,
        each of which can be either a C{string} or a C{DottedName}.
        Each piece is divided into a sequence of identifiers, and
        these sequences are combined together (in order) to form the
        identifier sequence for the new C{DottedName}.  If a piece
        contains a string, then it is divided into substrings by
        splitting on periods, and each substring is checked to see if
        it is a valid identifier.

        As an optimization, C{pieces} may also contain a single tuple
        of values.  In that case, that tuple will be used as the
        C{DottedName}'s identifiers; it will I{not} be checked to
        see if it's valid.

        @kwparam strict: if true, then raise an L{InvalidDottedName}
        if the given name is invalid.
        """
        if len(pieces) == 1 and isinstance(pieces[0], tuple):
            self._identifiers = pieces[0] # Optimization
            return
        if len(pieces) == 0:
            raise DottedName.InvalidDottedName('Empty DottedName')
        self._identifiers = []
        for piece in pieces:
            if isinstance(piece, DottedName):
                self._identifiers += piece._identifiers
            elif isinstance(piece, basestring):
                for subpiece in piece.split('.'):
                    if piece not in self._ok_identifiers:
                        if not self._IDENTIFIER_RE.match(subpiece):
                            if options.get('strict'):
                                raise DottedName.InvalidDottedName(
                                    'Bad identifier %r' % (piece,))
                            else:
                                log.warning("Identifier %r looks suspicious; "
                                            "using it anyway." % piece)
                        self._ok_identifiers.add(piece)
                    self._identifiers.append(subpiece)
            else:
                raise TypeError('Bad identifier %r: expected '
                                'DottedName or str' % (piece,))
        self._identifiers = tuple(self._identifiers)

    def __repr__(self):
        idents = [`ident` for ident in self._identifiers]
        return 'DottedName(' + ', '.join(idents) + ')'

    def __str__(self):
        """
        Return the dotted name as a string formed by joining its
        identifiers with periods:

            >>> print DottedName('epydoc', 'api_doc', DottedName')
            epydoc.apidoc.DottedName
        """
        return '.'.join(self._identifiers)

    def __add__(self, other):
        """
        Return a new C{DottedName} whose identifier sequence is formed
        by adding C{other}'s identifier sequence to C{self}'s.
        """
        if isinstance(other, (basestring, DottedName)):
            return DottedName(self, other)
        else:
            return DottedName(self, *other)

    def __radd__(self, other):
        """
        Return a new C{DottedName} whose identifier sequence is formed
        by adding C{self}'s identifier sequence to C{other}'s.
        """
        if isinstance(other, (basestring, DottedName)):
            return DottedName(other, self)
        else:
            return DottedName(*(list(other)+[self]))

    def __getitem__(self, i):
        """
        Return the C{i}th identifier in this C{DottedName}.  If C{i} is
        a non-empty slice, then return a C{DottedName} built from the
        identifiers selected by the slice.  If C{i} is an empty slice,
        return an empty list (since empty C{DottedName}s are not valid).
        """
        if isinstance(i, types.SliceType):
            pieces = self._identifiers[i.start:i.stop]
            if pieces: return DottedName(pieces)
            else: return []
        else:
            return self._identifiers[i]

    def __hash__(self):
        return hash(self._identifiers)

    def __cmp__(self, other):
        """
        Compare this dotted name to C{other}.  Two dotted names are
        considered equal if their identifier subsequences are equal.
        Ordering between dotted names is lexicographic, in order of
        identifier from left to right.
        """
        if not isinstance(other, DottedName):
            return -1
        return cmp(self._identifiers, other._identifiers)

    def __len__(self):
        """
        Return the number of identifiers in this dotted name.
        """
        return len(self._identifiers)

    def container(self):
        """
        Return the DottedName formed by removing the last identifier
        from this dotted name's identifier sequence.  If this dotted
        name only has one name in its identifier sequence, return
        C{None} instead.
        """
        if len(self._identifiers) == 1:
            return None
        else:
            return DottedName(*self._identifiers[:-1])

    def dominates(self, name, strict=False):
        """
        Return true if this dotted name is equal to a prefix of
        C{name}.  If C{strict} is true, then also require that
        C{self!=name}.

            >>> DottedName('a.b').dominates(DottedName('a.b.c.d'))
            True
        """
        len_self = len(self._identifiers)
        len_name = len(name._identifiers)

        if (len_self > len_name) or (strict and len_self == len_name):
            return False
        # The following is redundant (the first clause is implied by
        # the second), but is done as an optimization.
        return ((self._identifiers[0] == name._identifiers[0]) and
                self._identifiers == name._identifiers[:len_self])

    def contextualize(self, context):
        """
        If C{self} and C{context} share a common ancestor, then return
        a name for C{self}, relative to that ancestor.  If they do not
        share a common ancestor (or if C{context} is C{UNKNOWN}), then
        simply return C{self}.

        This is used to generate shorter versions of dotted names in
        cases where users can infer the intended target from the
        context.
        
        @type context: L{DottedName}
        @rtype: L{DottedName}
        """
        if context is UNKNOWN or not context or len(self) <= 1:
            return self
        if self[0] == context[0]:
            return self[1:].contextualize(context[1:])
        else:
            return self

        # Find the first index where self & context differ.
        for i in range(min(len(context), len(self))):
            if self._identifiers[i] != context._identifiers[i]:
                first_difference = i
                break
        else:
            first_difference = i+1
            
        # Strip off anything before that index.
        if first_difference == 0:
            return self
        elif first_difference == len(self):
            return self[-1:]
        else:
            return self[first_difference:]

######################################################################
# UNKNOWN Value
######################################################################

class _Sentinel:
    """
    A unique value that won't compare equal to any other value.  This
    class is used to create L{UNKNOWN}.
    """
    def __init__(self, name):
        self.name = name
    def __repr__(self):
        return '<%s>' % self.name
    def __nonzero__(self):
        raise ValueError('Sentinel value <%s> can not be used as a boolean' %
                         self.name)

UNKNOWN = _Sentinel('UNKNOWN')
"""A special value used to indicate that a given piece of
information about an object is unknown.  This is used as the
default value for all instance variables."""

######################################################################
# API Documentation Objects: Abstract Base Classes
######################################################################

class APIDoc(object):
    """
    API documentation information for a single element of a Python
    program.  C{APIDoc} itself is an abstract base class; subclasses
    are used to specify what information should be recorded about each
    type of program element.  In particular, C{APIDoc} has two direct
    subclasses, C{VariableDoc} for documenting variables and
    C{ValueDoc} for documenting values; and the C{ValueDoc} class is
    subclassed further for different value types.

    Each C{APIDoc} subclass specifies the set of attributes that
    should be used to record information about the corresponding
    program element type.  The default value for each attribute is
    stored in the class; these default values can then be overridden
    with instance variables.  Most attributes use the special value
    L{UNKNOWN} as their default value, to indicate that the correct
    value for that attribute has not yet been determined.  This makes
    it easier to merge two C{APIDoc} objects that are documenting the
    same element (in particular, to merge information about an element
    that was derived from parsing with information that was derived
    from introspection).

    For all attributes with boolean values, use only the constants
    C{True} and C{False} to designate true and false.  In particular,
    do I{not} use other values that evaluate as true or false, such as
    C{2} or C{()}.  This restriction makes it easier to handle
    C{UNKNOWN} values.  For example, to test if a boolean attribute is
    C{True} or C{UNKNOWN}, use 'C{attrib in (True, UNKNOWN)}' or
    'C{attrib is not False}'.

    Two C{APIDoc} objects describing the same object can be X{merged},
    using the method L{merge_and_overwrite(other)}.  After two
    C{APIDoc}s are merged, any changes to one will be reflected in the
    other.  This is accomplished by setting the two C{APIDoc} objects
    to use a shared instance dictionary.  See the documentation for
    L{merge_and_overwrite} for more information, and some important
    caveats about hashing.
    """
    #{ Docstrings
    docstring = UNKNOWN
    """@ivar: The documented item's docstring.
       @type: C{string} or C{None}"""
    
    docstring_lineno = UNKNOWN
    """@ivar: The line number on which the documented item's docstring
       begins.
       @type: C{int}"""
    #} end of "docstrings" group

    #{ Information Extracted from Docstrings
    descr = UNKNOWN
    """@ivar: A description of the documented item, extracted from its
       docstring.
       @type: L{ParsedDocstring<epydoc.markup.ParsedDocstring>}"""
    
    summary = UNKNOWN
    """@ivar: A summary description of the documented item, extracted from
       its docstring.
       @type: L{ParsedDocstring<epydoc.markup.ParsedDocstring>}"""
    
    other_docs = UNKNOWN
    """@ivar: A flag indicating if the entire L{docstring} body (except tags
       if any) is entirely included in the L{summary}.
       @type: C{bool}"""
    
    metadata = UNKNOWN
    """@ivar: Metadata about the documented item, extracted from fields in
       its docstring.  I{Currently} this is encoded as a list of tuples
       C{(field, arg, descr)}.  But that may change.
       @type: C{(str, str, L{ParsedDocstring<markup.ParsedDocstring>})}"""
    
    extra_docstring_fields = UNKNOWN
    """@ivar: A list of new docstring fields tags that are defined by the
       documented item's docstring.  These new field tags can be used by
       this item or by any item it contains.
       @type: L{DocstringField <epydoc.docstringparser.DocstringField>}"""
    #} end of "information extracted from docstrings" group

    #{ Source Information
    docs_extracted_by = UNKNOWN # 'parser' or 'introspecter' or 'both'
    """@ivar: Information about where the information contained by this
       C{APIDoc} came from.  Can be one of C{'parser'},
       C{'introspector'}, or C{'both'}.
       @type: C{str}"""
    #} end of "source information" group

    def __init__(self, **kwargs):
        """
        Construct a new C{APIDoc} object.  Keyword arguments may be
        used to initialize the new C{APIDoc}'s attributes.
        
        @raise TypeError: If a keyword argument is specified that does
            not correspond to a valid attribute for this (sub)class of
            C{APIDoc}.
        """
        if epydoc.DEBUG:
            for key in kwargs:
                if key[0] != '_' and not hasattr(self.__class__, key):
                    raise TypeError('%s got unexpected arg %r' %
                                    (self.__class__.__name__, key))
        self.__dict__.update(kwargs)

    def _debug_setattr(self, attr, val):
        """
        Modify an C{APIDoc}'s attribute.  This is used when
        L{epydoc.DEBUG} is true, to make sure we don't accidentally
        set any inappropriate attributes on C{APIDoc} objects.

        @raise AttributeError: If C{attr} is not a valid attribute for
            this (sub)class of C{APIDoc}.  (C{attr} is considered a
            valid attribute iff C{self.__class__} defines an attribute
            with that name.)
        """
        # Don't intercept special assignments like __class__, or
        # assignments to private variables.
        if attr.startswith('_'):
            return object.__setattr__(self, attr, val)
        if not hasattr(self, attr):
            raise AttributeError('%s does not define attribute %r' %
                            (self.__class__.__name__, attr))
        self.__dict__[attr] = val

    if epydoc.DEBUG:
        __setattr__ = _debug_setattr

    def __repr__(self):
       return '<%s>' % self.__class__.__name__
    
    def pp(self, doublespace=0, depth=5, exclude=(), include=()):
        """
        Return a pretty-printed string representation for the
        information contained in this C{APIDoc}.
        """
        return pp_apidoc(self, doublespace, depth, exclude, include)
    __str__ = pp

    def specialize_to(self, cls):
        """
        Change C{self}'s class to C{cls}.  C{cls} must be a subclass
        of C{self}'s current class.  For example, if a generic
        C{ValueDoc} was created for a value, and it is determined that
        the value is a routine, you can update its class with:
        
            >>> valdoc.specialize_to(RoutineDoc)
        """
        if not issubclass(cls, self.__class__):
            raise ValueError('Can not specialize to %r' % cls)
        # Update the class.
        self.__class__ = cls
        # Update the class of any other apidoc's in the mergeset.
        if self.__mergeset is not None:
            for apidoc in self.__mergeset:
                apidoc.__class__ = cls
        # Re-initialize self, in case the subclass constructor does
        # any special processing on its arguments.
        self.__init__(**self.__dict__)

    __has_been_hashed = False
    """True iff L{self.__hash__()} has ever been called."""
    
    def __hash__(self):
        self.__has_been_hashed = True
        return id(self.__dict__)

    def __cmp__(self, other):
        if not isinstance(other, APIDoc): return -1
        if self.__dict__ is other.__dict__: return 0
        name_cmp = cmp(self.canonical_name, other.canonical_name)
        if name_cmp == 0: return -1
        else: return name_cmp

    def is_detailed(self):
        """
        Does this object deserve a box with extra details?

        @return: True if the object needs extra details, else False.
        @rtype: C{bool}
        """
        if self.other_docs is True:
            return True

        if self.metadata is not UNKNOWN:
            return bool(self.metadata)

    __mergeset = None
    """The set of all C{APIDoc} objects that have been merged with
    this C{APIDoc} (using L{merge_and_overwrite()}).  Each C{APIDoc}
    in this set shares a common instance dictionary (C{__dict__})."""
    
    def merge_and_overwrite(self, other, ignore_hash_conflict=False):
        """
        Combine C{self} and C{other} into a X{merged object}, such
        that any changes made to one will affect the other.  Any
        attributes that C{other} had before merging will be discarded.
        This is accomplished by copying C{self.__dict__} over
        C{other.__dict__} and C{self.__class__} over C{other.__class__}.

        Care must be taken with this method, since it modifies the
        hash value of C{other}.  To help avoid the problems that this
        can cause, C{merge_and_overwrite} will raise an exception if
        C{other} has ever been hashed, unless C{ignore_hash_conflict}
        is True.  Note that adding C{other} to a dictionary, set, or
        similar data structure will implicitly cause it to be hashed.
        If you do set C{ignore_hash_conflict} to True, then any
        existing data structures that rely on C{other}'s hash staying
        constant may become corrupted.

        @return: C{self}
        @raise ValueError: If C{other} has ever been hashed.
        """
        # If we're already merged, then there's nothing to do.
        if (self.__dict__ is other.__dict__ and
            self.__class__ is other.__class__): return self
            
        if other.__has_been_hashed and not ignore_hash_conflict:
            raise ValueError("%r has already been hashed!  Merging it "
                             "would cause its has value to change." % other)

        # If other was itself already merged with anything,
        # then we need to merge those too.
        a,b = (self.__mergeset, other.__mergeset)
        mergeset = (self.__mergeset or [self]) + (other.__mergeset or [other])
        other.__dict__.clear()
        for apidoc in mergeset:
            #if apidoc is self: pass
            apidoc.__class__ = self.__class__
            apidoc.__dict__ = self.__dict__
        self.__mergeset = mergeset
        # Sanity chacks.
        assert self in mergeset and other in mergeset
        for apidoc in mergeset:
            assert apidoc.__dict__ is self.__dict__
        # Return self.
        return self

    def apidoc_links(self, **filters):
        """
        Return a list of all C{APIDoc}s that are directly linked from
        this C{APIDoc} (i.e., are contained or pointed to by one or
        more of this C{APIDoc}'s attributes.)

        Keyword argument C{filters} can be used to selectively exclude
        certain categories of attribute value.  For example, using
        C{includes=False} will exclude variables that were imported
        from other modules; and C{subclasses=False} will exclude
        subclasses.  The filter categories currently supported by
        epydoc are:
          - C{imports}: Imported variables.
          - C{packages}: Containing packages for modules.
          - C{submodules}: Contained submodules for packages.
          - C{bases}: Bases for classes.
          - C{subclasses}: Subclasses for classes.
          - C{variables}: All variables.
          - C{private}: Private variables.
          - C{overrides}: Points from class variables to the variables
            they override.  This filter is False by default.
        """
        return []

def reachable_valdocs(root, **filters):
    """
    Return a list of all C{ValueDoc}s that can be reached, directly or
    indirectly from the given root list of C{ValueDoc}s.

    @param filters: A set of filters that can be used to prevent
        C{reachable_valdocs} from following specific link types when
        looking for C{ValueDoc}s that can be reached from the root
        set.  See C{APIDoc.apidoc_links} for a more complete
        description.
    """
    apidoc_queue = list(root)
    val_set = set()
    var_set = set()
    while apidoc_queue:
        api_doc = apidoc_queue.pop()
        if isinstance(api_doc, ValueDoc):
            val_set.add(api_doc)
        else:
            var_set.add(api_doc)
        apidoc_queue.extend([v for v in api_doc.apidoc_links(**filters)
                             if v not in val_set and v not in var_set])
    return val_set

######################################################################
# Variable Documentation Objects
######################################################################

class VariableDoc(APIDoc):
    """
    API documentation information about a single Python variable.

    @note: The only time a C{VariableDoc} will have its own docstring
    is if that variable was created using an assignment statement, and
    that assignment statement had a docstring-comment or was followed
    by a pseudo-docstring.
    """
    #{ Basic Variable Information
    name = UNKNOWN
    """@ivar: The name of this variable in its containing namespace.
       @type: C{str}"""
    
    container = UNKNOWN
    """@ivar: API documentation for the namespace that contains this
       variable.
       @type: L{ValueDoc}"""
    
    canonical_name = UNKNOWN
    """@ivar: A dotted name that serves as a unique identifier for
       this C{VariableDoc}.  It should be formed by concatenating
       the C{VariableDoc}'s C{container} with its C{name}.
       @type: L{DottedName}"""

    value = UNKNOWN
    """@ivar: The API documentation for this variable's value.
       @type: L{ValueDoc}"""
    #}

    #{ Information Extracted from Docstrings
    type_descr = UNKNOWN 
    """@ivar: A description of the variable's expected type, extracted from
       its docstring.
       @type: L{ParsedDocstring<epydoc.markup.ParsedDocstring>}"""
    #} end of "information extracted from docstrings" group
    
    #{ Information about Imported Variables
    imported_from = UNKNOWN
    """@ivar: The fully qualified dotted name of the variable that this
       variable's value was imported from.  This attribute should only
       be defined if C{is_instvar} is true.
       @type: L{DottedName}"""

    is_imported = UNKNOWN
    """@ivar: Was this variable's value imported from another module?
       (Exception: variables that are explicitly included in __all__ have
       C{is_imported} set to C{False}, even if they are in fact
       imported.)
       @type: C{bool}"""
    #} end of "information about imported variables" group

    #{ Information about Variables in Classes
    is_instvar = UNKNOWN
    """@ivar: If true, then this variable is an instance variable; if false,
       then this variable is a class variable.  This attribute should
       only be defined if the containing namespace is a class    
       @type: C{bool}"""
    
    overrides = UNKNOWN # [XXX] rename -- don't use a verb.
    """@ivar: The API documentation for the variable that is overridden by
       this variable.  This attribute should only be defined if the
       containing namespace is a class.
       @type: L{VariableDoc}"""
    #} end of "information about variables in classes" group

    #{ Flags
    is_alias = UNKNOWN
    """@ivar: Is this variable an alias for another variable with the same
       value?  If so, then this variable will be dispreferred when
       assigning canonical names.
       @type: C{bool}"""
    
    is_public = UNKNOWN
    """@ivar: Is this variable part of its container's public API?
       @type: C{bool}"""
    #} end of "flags" group

    def __init__(self, **kwargs):
        APIDoc.__init__(self, **kwargs)
        if self.is_public is UNKNOWN and self.name is not UNKNOWN:
            self.is_public = (not self.name.startswith('_') or
                              self.name.endswith('_'))
        
    def __repr__(self):
        if self.canonical_name is not UNKNOWN:
            return '<%s %s>' % (self.__class__.__name__, self.canonical_name)
        if self.name is not UNKNOWN:
            return '<%s %s>' % (self.__class__.__name__, self.name)
        else:                     
            return '<%s>' % self.__class__.__name__

    def _get_defining_module(self):
        if self.container is UNKNOWN:
            return UNKNOWN
        return self.container.defining_module
    defining_module = property(_get_defining_module, doc="""
    A read-only property that can be used to get the variable's
    defining module.  This is defined as the defining module
    of the variable's container.""")

    def apidoc_links(self, **filters):
        # nb: overrides filter is *False* by default.
        if (filters.get('overrides', False) and
            (self.overrides not in (None, UNKNOWN))):
            overrides = [self.overrides]
        else:
            overrides = []
        if self.value in (None, UNKNOWN):
            return []+overrides
        else:
            return [self.value]+overrides

    def is_detailed(self):
        pval = super(VariableDoc, self).is_detailed()
        if pval or self.value in (None, UNKNOWN):
            return pval

        if (self.overrides not in (None, UNKNOWN) and
            isinstance(self.value, RoutineDoc)):
            return True

        if isinstance(self.value, GenericValueDoc):
            # [XX] This is a little hackish -- we assume that the
            # summary lines will have SUMMARY_REPR_LINELEN chars,
            # that len(name) of those will be taken up by the name,
            # and that 3 of those will be taken up by " = " between
            # the name & val.  Note that if any docwriter uses a
            # different formula for maxlen for this, then it will
            # not get the right value for is_detailed().
            maxlen = self.value.SUMMARY_REPR_LINELEN-3-len(self.name)
            return (not self.value.summary_pyval_repr(maxlen).is_complete)
        else:
            return self.value.is_detailed()

######################################################################
# Value Documentation Objects
######################################################################

class ValueDoc(APIDoc):
    """
    API documentation information about a single Python value.
    """
    canonical_name = UNKNOWN
    """@ivar: A dotted name that serves as a unique identifier for
       this C{ValueDoc}'s value.  If the value can be reached using a
       single sequence of identifiers (given the appropriate imports),
       then that sequence of identifiers is used as its canonical name.
       If the value can be reached by multiple sequences of identifiers
       (i.e., if it has multiple aliases), then one of those sequences of
       identifiers is used.  If the value cannot be reached by any
       sequence of identifiers (e.g., if it was used as a base class but
       then its variable was deleted), then its canonical name will start
       with C{'??'}.  If necessary, a dash followed by a number will be
       appended to the end of a non-reachable identifier to make its
       canonical name unique.

       When possible, canonical names are chosen when new C{ValueDoc}s
       are created.  However, this is sometimes not possible.  If a
       canonical name can not be chosen when the C{ValueDoc} is created,
       then one will be assigned by L{assign_canonical_names()
       <docbuilder.assign_canonical_names>}.
       
       @type: L{DottedName}"""

    #{ Value Representation
    pyval = UNKNOWN
    """@ivar: A pointer to the actual Python object described by this
       C{ValueDoc}.  This is used to display the value (e.g., when
       describing a variable.)  Use L{pyval_repr()} to generate a
       plaintext string representation of this value.
       @type: Python object"""

    parse_repr = UNKNOWN
    """@ivar: A text representation of this value, extracted from 
       parsing its source code.  This representation may not accurately
       reflect the actual value (e.g., if the value was modified after
       the initial assignment).
       @type: C{unicode}"""

    REPR_MAXLINES = 5
    """@cvar: The maximum number of lines of text that should be
    generated by L{pyval_repr()}.  If the string representation does
    not fit in this number of lines, an ellpsis marker (...) will
    be placed at the end of the formatted representation."""

    REPR_LINELEN = 75
    """@cvar: The maximum number of characters for lines of text that
    should be generated by L{pyval_repr()}.  Any lines that exceed
    this number of characters will be line-wrappped; The S{crarr}
    symbol will be used to indicate that the line was wrapped."""

    SUMMARY_REPR_LINELEN = 75
    """@cvar: The maximum number of characters for the single-line
    text representation generated by L{summary_pyval_repr()}.  If
    the value's representation does not fit in this number of
    characters, an ellipsis marker (...) will be placed at the end
    of the formatted representation."""

    REPR_MIN_SCORE = 0
    """@cvar: The minimum score that a value representation based on
    L{pyval} should have in order to be used instead of L{parse_repr}
    as the canonical representation for this C{ValueDoc}'s value.
    @see: L{epydoc.markup.pyval_repr}"""
    #} end of "value representation" group

    #{ Context
    defining_module = UNKNOWN
    """@ivar: The documentation for the module that defines this
       value.  This is used, e.g., to lookup the appropriate markup
       language for docstrings.  For a C{ModuleDoc},
       C{defining_module} should be C{self}.
       @type: L{ModuleDoc}"""
    #} end of "context group"

    #{ Information about Imported Variables
    proxy_for = None # [xx] in progress.
    """@ivar: If C{proxy_for} is not None, then this value was
       imported from another file.  C{proxy_for} is the dotted name of
       the variable that this value was imported from.  If that
       variable is documented, then its C{value} may contain more
       complete API documentation about this value.  The C{proxy_for}
       attribute is used by the source code parser to link imported
       values to their source values (in particular, for base
       classes).  When possible, these proxy C{ValueDoc}s are replaced
       by the imported value's C{ValueDoc} by
       L{link_imports()<docbuilder.link_imports>}.
       @type: L{DottedName}"""
    #} end of "information about imported variables" group

    #: @ivar:
    #: This is currently used to extract values from __all__, etc, in
    #: the docparser module; maybe I should specialize
    #: process_assignment and extract it there?  Although, for __all__,
    #: it's not clear where I'd put the value, since I just use it to
    #: set private/public/imported attribs on other vars (that might not
    #: exist yet at the time.)
    toktree = UNKNOWN

    def __repr__(self):
        if self.canonical_name is not UNKNOWN:
            return '<%s %s>' % (self.__class__.__name__, self.canonical_name)
        else:
            return '<%s %s>' % (self.__class__.__name__,
                                self.summary_pyval_repr().to_plaintext(None))

    def __setstate__(self, state):
        self.__dict__ = state

    def __getstate__(self):
        """
        State serializer for the pickle module.  This is necessary
        because sometimes the C{pyval} attribute contains an
        un-pickleable value.
        """
        # Construct our pickled dictionary.  Maintain this dictionary
        # as a private attribute, so we can reuse it later, since
        # merged objects need to share a single dictionary.
        if not hasattr(self, '_ValueDoc__pickle_state'):
            # Make sure __pyval_repr & __summary_pyval_repr are cached:
            self.pyval_repr(), self.summary_pyval_repr()
            # Construct the dictionary; leave out 'pyval'.
            self.__pickle_state = self.__dict__.copy()
            self.__pickle_state['pyval'] = UNKNOWN

        if not isinstance(self, GenericValueDoc):
            assert self.__pickle_state != {}
        # Return the pickle state.
        return self.__pickle_state

    #{ Value Representation
    def pyval_repr(self):
        """
        Return a formatted representation of the Python object
        described by this C{ValueDoc}.  This representation may
        include data from introspection or parsing, and is authorative
        as 'the best way to represent a Python value.'  Any lines that
        go beyond L{REPR_LINELEN} characters will be wrapped; and if
        the representation as a whole takes more than L{REPR_MAXLINES}
        lines, then it will be truncated (with an ellipsis marker).
        This function will never return L{UNKNOWN} or C{None}.
    
        @rtype: L{ColorizedPyvalRepr}
        """
        # Use self.__pyval_repr to cache the result.
        if not hasattr(self, '_ValueDoc__pyval_repr'):
            self.__pyval_repr = epydoc.markup.pyval_repr.colorize_pyval(
                self.pyval, self.parse_repr, self.REPR_MIN_SCORE,
                self.REPR_LINELEN, self.REPR_MAXLINES, linebreakok=True)
        return self.__pyval_repr

    def summary_pyval_repr(self, max_len=None):
        """
        Return a single-line formatted representation of the Python
        object described by this C{ValueDoc}.  This representation may
        include data from introspection or parsing, and is authorative
        as 'the best way to summarize a Python value.'  If the
        representation takes more then L{SUMMARY_REPR_LINELEN}
        characters, then it will be truncated (with an ellipsis
        marker).  This function will never return L{UNKNOWN} or
        C{None}.
    
        @rtype: L{ColorizedPyvalRepr}
        """
        # If max_len is specified, then do *not* cache the result.
        if max_len is not None:
            return epydoc.markup.pyval_repr.colorize_pyval(
                self.pyval, self.parse_repr, self.REPR_MIN_SCORE,
                max_len, maxlines=1, linebreakok=False)
            
        # Use self.__summary_pyval_repr to cache the result.
        if not hasattr(self, '_ValueDoc__summary_pyval_repr'):
            self.__summary_pyval_repr = epydoc.markup.pyval_repr.colorize_pyval(
                self.pyval, self.parse_repr, self.REPR_MIN_SCORE,
                self.SUMMARY_REPR_LINELEN, maxlines=1, linebreakok=False)
        return self.__summary_pyval_repr
    #} end of "value representation" group

    def apidoc_links(self, **filters):
        return []

class GenericValueDoc(ValueDoc):
    """
    API documentation about a 'generic' value, i.e., one that does not
    have its own docstring or any information other than its value and
    parse representation.  C{GenericValueDoc}s do not get assigned
    cannonical names.
    """
    canonical_name = None
    
    def is_detailed(self):
        return (not self.summary_pyval_repr().is_complete)

class NamespaceDoc(ValueDoc):
    """
    API documentation information about a singe Python namespace
    value.  (I.e., a module or a class).
    """
    #{ Information about Variables
    variables = UNKNOWN
    """@ivar: The contents of the namespace, encoded as a
        dictionary mapping from identifiers to C{VariableDoc}s.  This
        dictionary contains all names defined by the namespace,
        including imported variables, aliased variables, and variables
        inherited from base classes (once L{inherit_docs()
        <epydoc.docbuilder.inherit_docs>} has added them).
       @type: C{dict} from C{string} to L{VariableDoc}"""
    sorted_variables = UNKNOWN
    """@ivar: A list of all variables defined by this
       namespace, in sorted order.  The elements of this list should
       exactly match the values of L{variables}.  The sort order for
       this list is defined as follows:
          - Any variables listed in a C{@sort} docstring field are
            listed in the order given by that field.
          - These are followed by any variables that were found while
            parsing the source code, in the order in which they were
            defined in the source file.
          - Finally, any remaining variables are listed in
            alphabetical order.
       @type: C{list} of L{VariableDoc}"""
    sort_spec = UNKNOWN
    """@ivar: The order in which variables should be listed,
       encoded as a list of names.  Any variables whose names are not
       included in this list should be listed alphabetically,
       following the variables that are included.
       @type: C{list} of C{str}"""
    group_specs = UNKNOWN
    """@ivar: The groups that are defined by this namespace's
       docstrings.  C{group_specs} is encoded as an ordered list of
       tuples C{(group_name, elt_names)}, where C{group_name} is the
        
       name of a group and C{elt_names} is a list of element names in
       that group.  (An element can be a variable or a submodule.)  A
       '*' in an element name will match any string of characters.
       @type: C{list} of C{(str,list)}"""
    variable_groups = UNKNOWN
    """@ivar: A dictionary specifying what group each
       variable belongs to.  The keys of the dictionary are group
       names, and the values are lists of C{VariableDoc}s.  The order
       that groups should be listed in should be taken from
       L{group_specs}.
       @type: C{dict} from C{str} to C{list} of L{VariableDoc}"""
    #} end of group "information about variables"

    def __init__(self, **kwargs):
        kwargs.setdefault('variables', {})
        APIDoc.__init__(self, **kwargs)
        assert self.variables is not UNKNOWN

    def is_detailed(self):
        return True

    def apidoc_links(self, **filters):
        variables = filters.get('variables', True)
        imports = filters.get('imports', True)
        private = filters.get('private', True)
        if variables and imports and private:
            return self.variables.values() # list the common case first.
        elif not variables:
            return []
        elif not imports and not private:
            return [v for v in self.variables.values() if
                    v.is_imported != True and v.is_public != False]
        elif not private:
            return [v for v in self.variables.values() if
                    v.is_public != False]
        elif not imports:
            return [v for v in self.variables.values() if
                    v.is_imported != True]
        assert 0, 'this line should be unreachable'

    def init_sorted_variables(self):
        """
        Initialize the L{sorted_variables} attribute, based on the
        L{variables} and L{sort_spec} attributes.  This should usually
        be called after all variables have been added to C{variables}
        (including any inherited variables for classes).  
        """
        unsorted = self.variables.copy()
        self.sorted_variables = []
    
        # Add any variables that are listed in sort_spec
        if self.sort_spec is not UNKNOWN:
            unused_idents = set(self.sort_spec)
            for ident in self.sort_spec:
                if ident in unsorted:
                    self.sorted_variables.append(unsorted.pop(ident))
                    unused_idents.discard(ident)
                elif '*' in ident:
                    regexp = re.compile('^%s$' % ident.replace('*', '(.*)'))
                    # sort within matching group?
                    for name, var_doc in unsorted.items():
                        if regexp.match(name):
                            self.sorted_variables.append(unsorted.pop(name))
                            unused_idents.discard(ident)
            for ident in unused_idents:
                if ident not in ['__all__', '__docformat__', '__path__']:
                    log.warning("@sort: %s.%s not found" %
                                (self.canonical_name, ident))
                    
    
        # Add any remaining variables in alphabetical order.
        var_docs = unsorted.items()
        var_docs.sort()
        for name, var_doc in var_docs:
            self.sorted_variables.append(var_doc)

    def init_variable_groups(self):
        """
        Initialize the L{variable_groups} attribute, based on the
        L{sorted_variables} and L{group_specs} attributes.
        """
        if self.sorted_variables is UNKNOWN:
            self.init_sorted_variables()
        assert len(self.sorted_variables) == len(self.variables)

        elts = [(v.name, v) for v in self.sorted_variables]
        self._unused_groups = dict([(n,set(i)) for (n,i) in self.group_specs])
        self.variable_groups = self._init_grouping(elts)

    def group_names(self):
        """
        Return a list of the group names defined by this namespace, in
        the order in which they should be listed, with no duplicates.
        """
        name_list = ['']
        name_set = set()
        for name, spec in self.group_specs:
            if name not in name_set:
                name_set.add(name)
                name_list.append(name)
        return name_list

    def _init_grouping(self, elts):
        """
        Divide a given a list of APIDoc objects into groups, as
        specified by L{self.group_specs}.

        @param elts: A list of tuples C{(name, apidoc)}.
        
        @return: A list of tuples C{(groupname, elts)}, where
        C{groupname} is the name of a group and C{elts} is a list of
        C{APIDoc}s in that group.  The first tuple has name C{''}, and
        is used for ungrouped elements.  The remaining tuples are
        listed in the order that they appear in C{self.group_specs}.
        Within each tuple, the elements are listed in the order that
        they appear in C{api_docs}.
        """
        # Make the common case fast.
        if len(self.group_specs) == 0:
            return {'': [elt[1] for elt in elts]}

        ungrouped = set([elt_doc for (elt_name, elt_doc) in elts])

        ungrouped = dict(elts)
        groups = {}
        for elt_name, elt_doc in elts:
            for (group_name, idents) in self.group_specs:
                group = groups.setdefault(group_name, [])
                unused_groups = self._unused_groups[group_name]
                for ident in idents:
                    if re.match('^%s$' % ident.replace('*', '(.*)'), elt_name):
                        unused_groups.discard(ident)
                        if elt_name in ungrouped:
                            group.append(ungrouped.pop(elt_name))
                        else:
                            log.warning("%s.%s in multiple groups" %
                                        (self.canonical_name, elt_name))

        # Convert ungrouped from an unordered set to an ordered list.
        groups[''] = [elt_doc for (elt_name, elt_doc) in elts
                      if elt_name in ungrouped]
        return groups
    
    def report_unused_groups(self):
        """
        Issue a warning for any @group items that were not used by
        L{_init_grouping()}.
        """
        for (group, unused_idents) in self._unused_groups.items():
            for ident in unused_idents:
                log.warning("@group %s: %s.%s not found" %
                            (group, self.canonical_name, ident))
                        
class ModuleDoc(NamespaceDoc):
    """
    API documentation information about a single module.
    """
    #{ Information about the Module
    filename = UNKNOWN
    """@ivar: The name of the file that defines the module.
       @type: C{string}"""
    docformat = UNKNOWN
    """@ivar: The markup language used by docstrings in this module.
       @type: C{string}"""
    #{ Information about Submodules
    submodules = UNKNOWN
    """@ivar: Modules contained by this module (if this module
       is a package).  (Note: on rare occasions, a module may have a
       submodule that is shadowed by a variable with the same name.)
       @type: C{list} of L{ModuleDoc}"""
    submodule_groups = UNKNOWN
    """@ivar: A dictionary specifying what group each
       submodule belongs to.  The keys of the dictionary are group
       names, and the values are lists of C{ModuleDoc}s.  The order
       that groups should be listed in should be taken from
       L{group_specs}.
       @type: C{dict} from C{str} to C{list} of L{ModuleDoc}"""
    #{ Information about Packages
    package = UNKNOWN
    """@ivar: API documentation for the module's containing package.
       @type: L{ModuleDoc}"""
    is_package = UNKNOWN
    """@ivar: True if this C{ModuleDoc} describes a package.
       @type: C{bool}"""
    path = UNKNOWN
    """@ivar: If this C{ModuleDoc} describes a package, then C{path}
       contains a list of directories that constitute its path (i.e.,
       the value of its C{__path__} variable).
       @type: C{list} of C{str}"""
    #{ Information about Imported Variables
    imports = UNKNOWN
    """@ivar: A list of the source names of variables imported into
       this module.  This is used to construct import graphs.
       @type: C{list} of L{DottedName}"""
    #}

    def apidoc_links(self, **filters):
        val_docs = NamespaceDoc.apidoc_links(self, **filters)
        if (filters.get('packages', True) and
            self.package not in (None, UNKNOWN)):
            val_docs.append(self.package)
        if (filters.get('submodules', True) and
            self.submodules not in (None, UNKNOWN)):
            val_docs += self.submodules
        return val_docs

    def init_submodule_groups(self):
        """
        Initialize the L{submodule_groups} attribute, based on the
        L{submodules} and L{group_specs} attributes.
        """
        if self.submodules in (None, UNKNOWN):
            return
        self.submodules = sorted(self.submodules,
                                 key=lambda m:m.canonical_name)
        elts = [(m.canonical_name[-1], m) for m in self.submodules]
        self.submodule_groups = self._init_grouping(elts)

    def select_variables(self, group=None, value_type=None, public=None,
                         imported=None, detailed=None):
        """
        Return a specified subset of this module's L{sorted_variables}
        list.  If C{value_type} is given, then only return variables
        whose values have the specified type.  If C{group} is given,
        then only return variables that belong to the specified group.

        @require: The L{sorted_variables}, L{variable_groups}, and
            L{submodule_groups} attributes must be initialized before
            this method can be used.  See L{init_sorted_variables()},
            L{init_variable_groups()}, and L{init_submodule_groups()}.

        @param value_type: A string specifying the value type for
            which variables should be returned.  Valid values are:
              - 'class' - variables whose values are classes or types.
              - 'function' - variables whose values are functions.
              - 'other' - variables whose values are not classes,
                 exceptions, types, or functions.
        @type value_type: C{string}
        
        @param group: The name of the group for which variables should
            be returned.  A complete list of the groups defined by
            this C{ModuleDoc} is available in the L{group_names}
            instance variable.  The first element of this list is
            always the special group name C{''}, which is used for
            variables that do not belong to any group.
        @type group: C{string}

        @param detailed: If True (False), return only the variables
            deserving (not deserving) a detailed informative box.
            If C{None}, don't care.
        @type detailed: C{bool}
        """
        if (self.sorted_variables is UNKNOWN or 
            self.variable_groups is UNKNOWN):
            raise ValueError('sorted_variables and variable_groups '
                             'must be initialized first.')
        
        if group is None: var_list = self.sorted_variables
        else:
            var_list = self.variable_groups.get(group, self.sorted_variables)

        # Public/private filter (Count UNKNOWN as public)
        if public is True:
            var_list = [v for v in var_list if v.is_public is not False]
        elif public is False:
            var_list = [v for v in var_list if v.is_public is False]

        # Imported filter (Count UNKNOWN as non-imported)
        if imported is True:
            var_list = [v for v in var_list if v.is_imported is True]
        elif imported is False:
            var_list = [v for v in var_list if v.is_imported is not True]

        # Detailed filter
        if detailed is True:
            var_list = [v for v in var_list if v.is_detailed() is True]
        elif detailed is False:
            var_list = [v for v in var_list if v.is_detailed() is not True]

        # [xx] Modules are not currently included in any of these
        # value types.
        if value_type is None:
            return var_list
        elif value_type == 'class':
            return [var_doc for var_doc in var_list
                    if (isinstance(var_doc.value, ClassDoc))]
        elif value_type == 'function':
            return [var_doc for var_doc in var_list
                    if isinstance(var_doc.value, RoutineDoc)]
        elif value_type == 'other':
            return [var_doc for var_doc in var_list
                    if not isinstance(var_doc.value,
                                      (ClassDoc, RoutineDoc, ModuleDoc))]
        else:
            raise ValueError('Bad value type %r' % value_type)

class ClassDoc(NamespaceDoc):
    """
    API documentation information about a single class.
    """
    #{ Information about Base Classes
    bases = UNKNOWN
    """@ivar: API documentation for the class's base classes.
    @type: C{list} of L{ClassDoc}"""
    #{ Information about Subclasses
    subclasses = UNKNOWN
    """@ivar: API documentation for the class's known subclasses.
    @type: C{list} of L{ClassDoc}"""
    #}

    def apidoc_links(self, **filters):
        val_docs = NamespaceDoc.apidoc_links(self, **filters)
        if (filters.get('bases', True) and 
            self.bases not in (None, UNKNOWN)):
            val_docs += self.bases
        if (filters.get('subclasses', True) and
            self.subclasses not in (None, UNKNOWN)):
            val_docs += self.subclasses
        return val_docs
    
    def is_type(self):
        if self.canonical_name == DottedName('type'): return True
        if self.bases is UNKNOWN: return False
        for base in self.bases:
            if isinstance(base, ClassDoc) and base.is_type():
                return True
        return False
    
    def is_exception(self):
        if self.canonical_name == DottedName('Exception'): return True
        if self.bases is UNKNOWN: return False
        for base in self.bases:
            if isinstance(base, ClassDoc) and base.is_exception():
                return True
        return False
    
    def is_newstyle_class(self):
        if self.canonical_name == DottedName('object'): return True
        if self.bases is UNKNOWN: return False
        for base in self.bases:
            if isinstance(base, ClassDoc) and base.is_newstyle_class():
                return True
        return False

    def mro(self, warn_about_bad_bases=False):
        if self.is_newstyle_class():
            return self._c3_mro(warn_about_bad_bases)
        else:
            return self._dfs_bases([], set(), warn_about_bad_bases)
                
    def _dfs_bases(self, mro, seen, warn_about_bad_bases):
        if self in seen: return mro
        mro.append(self)
        seen.add(self)
        if self.bases is not UNKNOWN:
            for base in self.bases:
                if isinstance(base, ClassDoc) and base.proxy_for is None:
                    base._dfs_bases(mro, seen, warn_about_bad_bases)
                elif warn_about_bad_bases:
                    self._report_bad_base(base)
        return mro

    def _c3_mro(self, warn_about_bad_bases):
        """
        Compute the class precedence list (mro) according to C3.
        @seealso: U{http://www.python.org/2.3/mro.html}
        """
        bases = [base for base in self.bases if isinstance(base, ClassDoc)]
        if len(bases) != len(self.bases) and warn_about_bad_bases:
            for base in self.bases:
                if (not isinstance(base, ClassDoc) or
                    base.proxy_for is not None):
                    self._report_bad_base(base)
        w = [warn_about_bad_bases]*len(bases)
        return self._c3_merge([[self]] + map(ClassDoc._c3_mro, bases, w) +
                              [list(bases)])

    def _report_bad_base(self, base):
        if not isinstance(base, ClassDoc):
            if not isinstance(base, GenericValueDoc):
                base_name = base.canonical_name
            elif base.parse_repr is not UNKNOWN:
                base_name = base.parse_repr
            else:
                base_name = '%r' % base
            log.warning("%s's base %s is not a class" %
                        (self.canonical_name, base_name))
        elif base.proxy_for is not None:
            log.warning("No information available for %s's base %s" %
                        (self.canonical_name, base.proxy_for))

    def _c3_merge(self, seqs):
        """
        Helper function for L{_c3_mro}.
        """
        res = []
        while 1:
          nonemptyseqs=[seq for seq in seqs if seq]
          if not nonemptyseqs: return res
          for seq in nonemptyseqs: # find merge candidates among seq heads
              cand = seq[0]
              nothead=[s for s in nonemptyseqs if cand in s[1:]]
              if nothead: cand=None #reject candidate
              else: break
          if not cand: raise TypeError("Inconsistent hierarchy")
          res.append(cand)
          for seq in nonemptyseqs: # remove cand
              if seq[0] == cand: del seq[0]
    
    def select_variables(self, group=None, value_type=None, inherited=None,
                         public=None, imported=None, detailed=None):
        """
        Return a specified subset of this class's L{sorted_variables}
        list.  If C{value_type} is given, then only return variables
        whose values have the specified type.  If C{group} is given,
        then only return variables that belong to the specified group.
        If C{inherited} is True, then only return inherited variables;
        if C{inherited} is False, then only return local variables.

        @require: The L{sorted_variables} and L{variable_groups}
            attributes must be initialized before this method can be
            used.  See L{init_sorted_variables()} and
            L{init_variable_groups()}.

        @param value_type: A string specifying the value type for
            which variables should be returned.  Valid values are:
              - 'instancemethod' - variables whose values are
                instance methods.
              - 'classmethod' - variables whose values are class
                methods.
              - 'staticmethod' - variables whose values are static
                methods.
              - 'properties' - variables whose values are properties.
              - 'class' - variables whose values are nested classes
                (including exceptions and types).
              - 'instancevariable' - instance variables.  This includes
                any variables that are explicitly marked as instance
                variables with docstring fields; and variables with
                docstrings that are initialized in the constructor.
              - 'classvariable' - class variables.  This includes any
                variables that are not included in any of the above
                categories.
        @type value_type: C{string}
        
        @param group: The name of the group for which variables should
            be returned.  A complete list of the groups defined by
            this C{ClassDoc} is available in the L{group_names}
            instance variable.  The first element of this list is
            always the special group name C{''}, which is used for
            variables that do not belong to any group.
        @type group: C{string}

        @param inherited: If C{None}, then return both inherited and
            local variables; if C{True}, then return only inherited
            variables; if C{False}, then return only local variables.

        @param detailed: If True (False), return only the variables
            deserving (not deserving) a detailed informative box.
            If C{None}, don't care.
        @type detailed: C{bool}
        """
        if (self.sorted_variables is UNKNOWN or 
            self.variable_groups is UNKNOWN):
            raise ValueError('sorted_variables and variable_groups '
                             'must be initialized first.')
        
        if group is None: var_list = self.sorted_variables
        else: var_list = self.variable_groups[group]

        # Public/private filter (Count UNKNOWN as public)
        if public is True:
            var_list = [v for v in var_list if v.is_public is not False]
        elif public is False:
            var_list = [v for v in var_list if v.is_public is False]

        # Inherited filter (Count UNKNOWN as non-inherited)
        if inherited is None: pass
        elif inherited:
            var_list = [v for v in var_list if v.container != self]
        else:
            var_list = [v for v in var_list if v.container == self ]

        # Imported filter (Count UNKNOWN as non-imported)
        if imported is True:
            var_list = [v for v in var_list if v.is_imported is True]
        elif imported is False:
            var_list = [v for v in var_list if v.is_imported is not True]

        # Detailed filter
        if detailed is True:
            var_list = [v for v in var_list if v.is_detailed() is True]
        elif detailed is False:
            var_list = [v for v in var_list if v.is_detailed() is not True]

        if value_type is None:
            return var_list
        elif value_type == 'method':
            return [var_doc for var_doc in var_list
                    if (isinstance(var_doc.value, RoutineDoc) and
                        var_doc.is_instvar in (False, UNKNOWN))]
        elif value_type == 'instancemethod':
            return [var_doc for var_doc in var_list
                    if (isinstance(var_doc.value, RoutineDoc) and
                        not isinstance(var_doc.value, ClassMethodDoc) and
                        not isinstance(var_doc.value, StaticMethodDoc) and
                        var_doc.is_instvar in (False, UNKNOWN))]
        elif value_type == 'classmethod':
            return [var_doc for var_doc in var_list
                    if (isinstance(var_doc.value, ClassMethodDoc) and
                        var_doc.is_instvar in (False, UNKNOWN))]
        elif value_type == 'staticmethod':
            return [var_doc for var_doc in var_list
                    if (isinstance(var_doc.value, StaticMethodDoc) and
                        var_doc.is_instvar in (False, UNKNOWN))]
        elif value_type == 'property':
            return [var_doc for var_doc in var_list
                    if (isinstance(var_doc.value, PropertyDoc) and
                        var_doc.is_instvar in (False, UNKNOWN))]
        elif value_type == 'class':
            return [var_doc for var_doc in var_list
                    if (isinstance(var_doc.value, ClassDoc) and
                        var_doc.is_instvar in (False, UNKNOWN))]
        elif value_type == 'instancevariable':
            return [var_doc for var_doc in var_list
                    if var_doc.is_instvar is True]
        elif value_type == 'classvariable':
            return [var_doc for var_doc in var_list
                    if (var_doc.is_instvar in (False, UNKNOWN) and
                        not isinstance(var_doc.value,
                                       (RoutineDoc, ClassDoc, PropertyDoc)))]
        else:
            raise ValueError('Bad value type %r' % value_type)

class RoutineDoc(ValueDoc):
    """
    API documentation information about a single routine.
    """
    #{ Signature
    posargs = UNKNOWN
    """@ivar: The names of the routine's positional arguments.
       If an argument list contains \"unpacking\" arguments, then
       their names will be specified using nested lists.  E.g., if
       a function's argument list is C{((x1,y1), (x2,y2))}, then
       posargs will be C{[['x1','y1'], ['x2','y2']]}.
       @type: C{list}"""
    posarg_defaults = UNKNOWN
    """@ivar: API documentation for the positional arguments'
       default values.  This list has the same length as C{posargs}, and
       each element of C{posarg_defaults} describes the corresponding
       argument in C{posargs}.  For positional arguments with no default,
       C{posargs_defaults} will contain None.
       @type: C{list} of C{ValueDoc} or C{None}"""
    vararg = UNKNOWN
    """@ivar: The name of the routine's vararg argument, or C{None} if
       it has no vararg argument.
       @type: C{string} or C{None}"""
    kwarg = UNKNOWN
    """@ivar: The name of the routine's keyword argument, or C{None} if
       it has no keyword argument.
       @type: C{string} or C{None}"""
    lineno = UNKNOWN # used to look up profiling info from pstats.
    """@ivar: The line number of the first line of the function's
       signature.  For Python functions, this is equal to
       C{func.func_code.co_firstlineno}.  The first line of a file
       is considered line 1.
       @type: C{int}"""
    #} end of "signature" group

    #{ Decorators
    decorators = UNKNOWN
    """@ivar: A list of names of decorators that were applied to this
       routine, in the order that they are listed in the source code.
       (I.e., in the reverse of the order that they were applied in.)
       @type: C{list} of C{string}"""
    #} end of "decorators" group

    #{ Information Extracted from Docstrings
    arg_descrs = UNKNOWN
    """@ivar: A list of descriptions of the routine's
       arguments.  Each element of this list is a tuple C{(args,
       descr)}, where C{args} is a list of argument names; and
       C{descr} is a L{ParsedDocstring
       <epydoc.markup.ParsedDocstring>} describing the argument(s)
       specified by C{arg}.
       @type: C{list}"""
    arg_types = UNKNOWN
    """@ivar: Descriptions of the expected types for the
       routine's arguments, encoded as a dictionary mapping from
       argument names to type descriptions.
       @type: C{dict} from C{string} to L{ParsedDocstring
       <epydoc.markup.ParsedDocstring>}"""
    return_descr = UNKNOWN
    """@ivar: A description of the value returned by this routine.
       @type: L{ParsedDocstring<epydoc.markup.ParsedDocstring>}"""
    return_type = UNKNOWN
    """@ivar: A description of expected type for the value
       returned by this routine.
       @type: L{ParsedDocstring<epydoc.markup.ParsedDocstring>}"""
    exception_descrs = UNKNOWN
    """@ivar: A list of descriptions of exceptions
       that the routine might raise.  Each element of this list is a
       tuple C{(exc, descr)}, where C{exc} is a string contianing the
       exception name; and C{descr} is a L{ParsedDocstring
       <epydoc.markup.ParsedDocstring>} describing the circumstances
       under which the exception specified by C{exc} is raised.
       @type: C{list}"""
    #} end of "information extracted from docstrings" group
    callgraph_uid = None
    """@ivar: L{DotGraph}.uid of the call graph for the function.
       @type: C{str}"""

    def is_detailed(self):
        if super(RoutineDoc, self).is_detailed():
            return True

        if self.arg_descrs not in (None, UNKNOWN) and self.arg_descrs:
            return True

        if self.arg_types not in (None, UNKNOWN) and self.arg_types:
            return True

        if self.return_descr not in (None, UNKNOWN):
            return True

        if self.exception_descrs not in (None, UNKNOWN) and self.exception_descrs:
            return True

        if (self.decorators not in (None, UNKNOWN)
            and [ d for d in self.decorators
                 if d not in ('classmethod', 'staticmethod') ]):
            return True

        return False

    def all_args(self):
        """
        @return: A list of the names of all arguments (positional,
        vararg, and keyword), in order.  If a positional argument
        consists of a tuple of names, then that tuple will be
        flattened.
        """
        if self.posargs is UNKNOWN:
            return UNKNOWN
            
        all_args = _flatten(self.posargs)
        if self.vararg not in (None, UNKNOWN):
            all_args.append(self.vararg)
        if self.kwarg not in (None, UNKNOWN):
            all_args.append(self.kwarg)
        return all_args

def _flatten(lst, out=None):
    """
    Return a flattened version of C{lst}.
    """
    if out is None: out = []
    for elt in lst:
        if isinstance(elt, (list,tuple)):
            _flatten(elt, out)
        else:
            out.append(elt)
    return out

class ClassMethodDoc(RoutineDoc): pass
class StaticMethodDoc(RoutineDoc): pass

class PropertyDoc(ValueDoc):
    """
    API documentation information about a single property.
    """
    #{ Property Access Functions
    fget = UNKNOWN
    """@ivar: API documentation for the property's get function.
       @type: L{RoutineDoc}"""
    fset = UNKNOWN
    """@ivar: API documentation for the property's set function.
       @type: L{RoutineDoc}"""
    fdel = UNKNOWN
    """@ivar: API documentation for the property's delete function.
       @type: L{RoutineDoc}"""
    #}
    #{ Information Extracted from Docstrings
    type_descr = UNKNOWN
    """@ivar: A description of the property's expected type, extracted
       from its docstring.
       @type: L{ParsedDocstring<epydoc.markup.ParsedDocstring>}"""
    #} end of "information extracted from docstrings" group

    def apidoc_links(self, **filters):
        val_docs = []
        if self.fget not in (None, UNKNOWN): val_docs.append(self.fget)
        if self.fset not in (None, UNKNOWN): val_docs.append(self.fset)
        if self.fdel not in (None, UNKNOWN): val_docs.append(self.fdel)
        return val_docs

    def is_detailed(self):
        if super(PropertyDoc, self).is_detailed():
            return True

        if self.fget not in (None, UNKNOWN) and self.fget.pyval is not None:
             return True
        if self.fset not in (None, UNKNOWN) and self.fset.pyval is not None:
             return True
        if self.fdel not in (None, UNKNOWN) and self.fdel.pyval is not None:
             return True

        return False

######################################################################
## Index
######################################################################

class DocIndex:
    """
    [xx] out of date.
    
    An index that .. hmm...  it *can't* be used to access some things,
    cuz they're not at the root level.  Do I want to add them or what?
    And if so, then I have a sort of a new top level.  hmm..  so
    basically the question is what to do with a name that's not in the
    root var's name space.  2 types:
      - entirely outside (eg os.path)
      - inside but not known (eg a submodule that we didn't look at?)
      - container of current thing not examined?
    
    An index of all the C{APIDoc} objects that can be reached from a
    root set of C{ValueDoc}s.  
    
    The members of this index can be accessed by dotted name.  In
    particular, C{DocIndex} defines two mappings, accessed via the
    L{get_vardoc()} and L{get_valdoc()} methods, which can be used to
    access C{VariableDoc}s or C{ValueDoc}s respectively by name.  (Two
    separate mappings are necessary because a single name can be used
    to refer to both a variable and to the value contained by that
    variable.)

    Additionally, the index defines two sets of C{ValueDoc}s:
    \"reachable C{ValueDoc}s\" and \"contained C{ValueDoc}s\".  The
    X{reachable C{ValueDoc}s} are defined as the set of all
    C{ValueDoc}s that can be reached from the root set by following
    I{any} sequence of pointers to C{ValueDoc}s or C{VariableDoc}s.
    The X{contained C{ValueDoc}s} are defined as the set of all
    C{ValueDoc}s that can be reached from the root set by following
    only the C{ValueDoc} pointers defined by non-imported
    C{VariableDoc}s.  For example, if the root set contains a module
    C{m}, then the contained C{ValueDoc}s includes the C{ValueDoc}s
    for any functions, variables, or classes defined in that module,
    as well as methods and variables defined in classes defined in the
    module.  The reachable C{ValueDoc}s includes all of those
    C{ValueDoc}s, as well as C{ValueDoc}s for any values imported into
    the module, and base classes for classes defined in the module.
    """

    def __init__(self, root):
        """
        Create a new documentation index, based on the given root set
        of C{ValueDoc}s.  If any C{APIDoc}s reachable from the root
        set does not have a canonical name, then it will be assigned
        one.  etc.
        
        @param root: A list of C{ValueDoc}s.
        """
        for apidoc in root:
            if apidoc.canonical_name in (None, UNKNOWN):
                raise ValueError("All APIdocs passed to DocIndexer "
                                 "must already have canonical names.")
        
        # Initialize the root items list.  We sort them by length in
        # ascending order.  (This ensures that variables will shadow
        # submodules when appropriate.)
        # When the elements name is the same, list in alphabetical order:
        # this is needed by the check for duplicates below.
        self.root = sorted(root,
            key=lambda d: (len(d.canonical_name), d.canonical_name))
        """The list of C{ValueDoc}s to document.
            @type: C{list}"""

        # Drop duplicated modules
        # [xx] maybe what causes duplicates should be fixed instead.
        #      If fixed, adjust the sort here above: sorting by names will not
        #      be required anymore
        i = 1
        while i < len(self.root):
            if self.root[i-1] is self.root[i]:
                del self.root[i]
            else:
                i += 1

        self.mlclasses = self._get_module_classes(self.root)
        """A mapping from class names to L{ClassDoc}. Contains
           classes defined at module level for modules in L{root}
           and which can be used as fallback by L{find()} if looking
           in containing namespaces fails.
           @type: C{dict} from C{str} to L{ClassDoc} or C{list}"""

        self.callers = None
        """A dictionary mapping from C{RoutineDoc}s in this index
           to lists of C{RoutineDoc}s for the routine's callers.
           This dictionary is initialized by calling
           L{read_profiling_info()}.
           @type: C{list} of L{RoutineDoc}"""
        
        self.callees = None
        """A dictionary mapping from C{RoutineDoc}s in this index
           to lists of C{RoutineDoc}s for the routine's callees.
           This dictionary is initialized by calling
           L{read_profiling_info()}.
           @type: C{list} of L{RoutineDoc}"""

        self._funcid_to_doc = {}
        """A mapping from C{profile} function ids to corresponding
           C{APIDoc} objects.  A function id is a tuple of the form
           C{(filename, lineno, funcname)}.  This is used to update
           the L{callers} and L{callees} variables."""

        self._container_cache = {}
        """A cache for the L{container()} method, to increase speed."""

        self._get_cache = {}
        """A cache for the L{get_vardoc()} and L{get_valdoc()} methods,
        to increase speed."""

    #////////////////////////////////////////////////////////////
    # Lookup methods
    #////////////////////////////////////////////////////////////
    # [xx]
    # Currently these only work for things reachable from the
    # root... :-/  I might want to change this so that imported
    # values can be accessed even if they're not contained.  
    # Also, I might want canonical names to not start with ??
    # if the thing is a top-level imported module..?

    def get_vardoc(self, name):
        """
        Return the C{VariableDoc} with the given name, or C{None} if this
        index does not contain a C{VariableDoc} with the given name.
        """
        var, val = self._get(name)
        return var

    def get_valdoc(self, name):
        """
        Return the C{ValueDoc} with the given name, or C{None} if this
        index does not contain a C{ValueDoc} with the given name.
        """
        var, val = self._get(name)
        return val

    def _get(self, name):
        """
        A helper function that's used to implement L{get_vardoc()}
        and L{get_valdoc()}.
        """
        # Convert name to a DottedName, if necessary.
        if not isinstance(name, DottedName):
            name = DottedName(name)

        # Check if the result is cached.
        val = self._get_cache.get(name)
        if val is not None: return val

        # Look for an element in the root set whose name is a prefix
        # of `name`.  If we can't find one, then return None.
        for root_valdoc in self.root:
            if root_valdoc.canonical_name.dominates(name):
                # Starting at the root valdoc, walk down the variable/
                # submodule chain until we find the requested item.
                var_doc = None
                val_doc = root_valdoc
                for identifier in name[len(root_valdoc.canonical_name):]:
                    if val_doc is None: break
                    var_doc, val_doc = self._get_from(val_doc, identifier)
                else:
                    # If we found it, then return.
                    if var_doc is not None or val_doc is not None:
                        self._get_cache[name] = (var_doc, val_doc)
                        return var_doc, val_doc

        # We didn't find it.
        self._get_cache[name] = (None, None)
        return None, None

    def _get_from(self, val_doc, identifier):
        if isinstance(val_doc, NamespaceDoc):
            child_var = val_doc.variables.get(identifier)
            if child_var is not None:
                child_val = child_var.value
                if child_val is UNKNOWN: child_val = None
                return child_var, child_val

        # If that fails, then see if it's a submodule.
        if (isinstance(val_doc, ModuleDoc) and
            val_doc.submodules is not UNKNOWN):
            for submodule in val_doc.submodules:
                if submodule.canonical_name[-1] == identifier:
                    var_doc = None
                    val_doc = submodule
                    if val_doc is UNKNOWN: val_doc = None
                    return var_doc, val_doc

        return None, None

    def find(self, name, context):
        """
        Look for an C{APIDoc} named C{name}, relative to C{context}.
        Return the C{APIDoc} if one is found; otherwise, return
        C{None}.  C{find} looks in the following places, in order:
          - Function parameters (if one matches, return C{None})
          - All enclosing namespaces, from closest to furthest.
          - If C{name} starts with C{'self'}, then strip it off and
            look for the remaining part of the name using C{find}
          - Builtins
          - Parameter attributes
          - Classes at module level (if the name is not ambiguous)
        
        @type name: C{str} or L{DottedName}
        @type context: L{APIDoc}
        """
        if isinstance(name, basestring):
            name = re.sub(r'\(.*\)$', '', name.strip())
            if re.match('^([a-zA-Z_]\w*)(\.[a-zA-Z_]\w*)*$', name):
                name = DottedName(name)
            else:
                return None
        elif not isinstance(name, DottedName):
            raise TypeError("'name' should be a string or DottedName")
        
        if context is None or context.canonical_name is None:
            container_name = []
        else:
            container_name = context.canonical_name

        # Check for the name in all containing namespaces, starting
        # with the closest one.
        for i in range(len(container_name), -1, -1):
            relative_name = container_name[:i]+name
            # Is `name` the absolute name of a documented value?
            # (excepting GenericValueDoc values.)
            val_doc = self.get_valdoc(relative_name)
            if (val_doc is not None and
                not isinstance(val_doc, GenericValueDoc)):
                return val_doc
            # Is `name` the absolute name of a documented variable?
            var_doc = self.get_vardoc(relative_name)
            if var_doc is not None: return var_doc

        # If the name begins with 'self', then try stripping that off
        # and see if we can find the variable.
        if name[0] == 'self':
            doc = self.find('.'.join(name[1:]), context)
            if doc is not None: return doc

        # Is it the name of a builtin?
        if len(name)==1 and hasattr(__builtin__, name[0]):
            return None
        
        # Is it a parameter's name or an attribute of a parameter?
        if isinstance(context, RoutineDoc):
            all_args = context.all_args()
            if all_args is not UNKNOWN and name[0] in all_args:
                return None

        # Is this an object directly contained by any module?
        doc = self.mlclasses.get(name[-1])
        if isinstance(doc, APIDoc):
            return doc
        elif isinstance(doc, list):
            log.warning("%s is an ambiguous name: it may be %s" % (
                name[-1],
                ", ".join([ "'%s'" % d.canonical_name for d in doc ])))

            # Drop this item so that the warning is reported only once.
            # fail() will fail anyway.
            del self.mlclasses[name[-1]]

    def _get_module_classes(self, docs):
        """
        Gather all the classes defined in a list of modules.

        Very often people refers to classes only by class name,
        even if they are not imported in the namespace. Linking
        to such classes will fail if we look for them only in nested
        namespaces. Allow them to retrieve only by name.

        @param docs: containers of the objects to collect
        @type docs: C{list} of C{APIDoc}
        @return: mapping from objects name to the object(s) with that name
        @rtype: C{dict} from C{str} to L{ClassDoc} or C{list}
        """
        classes = {}
        for doc in docs:
            if not isinstance(doc, ModuleDoc):
                continue

            for var in doc.variables.values():
                if not isinstance(var.value, ClassDoc):
                    continue

                val = var.value
                if val in (None, UNKNOWN) or val.defining_module is not doc:
                    continue
                if val.canonical_name in (None, UNKNOWN):
                    continue

                name = val.canonical_name[-1]
                vals = classes.get(name)
                if vals is None:
                    classes[name] = val
                elif not isinstance(vals, list):
                    classes[name] = [ vals, val ]
                else:
                    vals.append(val)

        return classes

    #////////////////////////////////////////////////////////////
    # etc
    #////////////////////////////////////////////////////////////

    def reachable_valdocs(self, **filters):
        """
        Return a list of all C{ValueDoc}s that can be reached,
        directly or indirectly from this C{DocIndex}'s root set.
        
        @param filters: A set of filters that can be used to prevent
            C{reachable_valdocs} from following specific link types
            when looking for C{ValueDoc}s that can be reached from the
            root set.  See C{APIDoc.apidoc_links} for a more complete
            description.
        """
        return reachable_valdocs(self.root, **filters)

    def container(self, api_doc):
        """
        Return the C{ValueDoc} that contains the given C{APIDoc}, or
        C{None} if its container is not in the index.
        """
        # Check if the result is cached.
        val = self._container_cache.get(api_doc)
        if val is not None: return val
        
        if isinstance(api_doc, GenericValueDoc):
            self._container_cache[api_doc] = None
            return None # [xx] unknown.
        if isinstance(api_doc, VariableDoc):
            self._container_cache[api_doc] = api_doc.container
            return api_doc.container
        if len(api_doc.canonical_name) == 1:
            self._container_cache[api_doc] = None
            return None
        elif isinstance(api_doc, ModuleDoc) and api_doc.package is not UNKNOWN:
            self._container_cache[api_doc] = api_doc.package
            return api_doc.package
        else:
            parent = self.get_valdoc(api_doc.canonical_name.container())
            self._container_cache[api_doc] = parent
            return parent

    #////////////////////////////////////////////////////////////
    # Profiling information
    #////////////////////////////////////////////////////////////

    def read_profiling_info(self, profile_stats):
        """
        Initialize the L{callers} and L{callees} variables, given a
        C{Stat} object from the C{pstats} module.
        
        @warning: This method uses undocumented data structures inside
            of C{profile_stats}.
        """
        if self.callers is None: self.callers = {}
        if self.callees is None: self.callees = {}
        
        # The Stat object encodes functions using `funcid`s, or
        # tuples of (filename, lineno, funcname).  Create a mapping
        # from these `funcid`s to `RoutineDoc`s.
        self._update_funcid_to_doc(profile_stats)
        
        for callee, (cc, nc, tt, ct, callers) in profile_stats.stats.items():
            callee = self._funcid_to_doc.get(callee)
            if callee is None: continue
            for caller in callers:
                caller = self._funcid_to_doc.get(caller)
                if caller is None: continue
                self.callers.setdefault(callee, []).append(caller)
                self.callees.setdefault(caller, []).append(callee)

    def _update_funcid_to_doc(self, profile_stats):
        """
        Update the dictionary mapping from C{pstat.Stat} funciton ids to
        C{RoutineDoc}s.  C{pstat.Stat} function ids are tuples of
        C{(filename, lineno, funcname)}.
        """
        # Maps (filename, lineno, funcname) -> RoutineDoc
        for val_doc in self.reachable_valdocs():
            # We only care about routines.
            if not isinstance(val_doc, RoutineDoc): continue
            # Get the filename from the defining module.
            module = val_doc.defining_module
            if module is UNKNOWN or module.filename is UNKNOWN: continue
            # Normalize the filename.
            filename = os.path.abspath(module.filename)
            try: filename = py_src_filename(filename)
            except: pass
            # Look up the stat_func_id
            funcid = (filename, val_doc.lineno, val_doc.canonical_name[-1])
            if funcid in profile_stats.stats:
                self._funcid_to_doc[funcid] = val_doc

######################################################################
## Pretty Printing
######################################################################

def pp_apidoc(api_doc, doublespace=0, depth=5, exclude=(), include=(),
              backpointers=None):
    """
    @return: A multiline pretty-printed string representation for the
        given C{APIDoc}.
    @param doublespace: If true, then extra lines will be
        inserted to make the output more readable.
    @param depth: The maximum depth that pp_apidoc will descend
        into descendent VarDocs.  To put no limit on
        depth, use C{depth=-1}.
    @param exclude: A list of names of attributes whose values should
        not be shown.
    @param backpointers: For internal use.
    """
    pyid = id(api_doc.__dict__)
    if backpointers is None: backpointers = {}
    if (hasattr(api_doc, 'canonical_name') and
        api_doc.canonical_name not in (None, UNKNOWN)):
        name = '%s for %s' % (api_doc.__class__.__name__,
                              api_doc.canonical_name)
    elif getattr(api_doc, 'name', None) not in (UNKNOWN, None):
        if (getattr(api_doc, 'container', None) not in (UNKNOWN, None) and
            getattr(api_doc.container, 'canonical_name', None)
            not in (UNKNOWN, None)):
            name ='%s for %s' % (api_doc.__class__.__name__,
                                 api_doc.container.canonical_name+
                                 api_doc.name)
        else:
            name = '%s for %s' % (api_doc.__class__.__name__, api_doc.name)
    else:
        name = api_doc.__class__.__name__
        
    if pyid in backpointers:
        return '%s [%s] (defined above)' % (name, backpointers[pyid])
    
    if depth == 0:
        if hasattr(api_doc, 'name') and api_doc.name is not None:
            return '%s...' % api_doc.name
        else:
            return '...'

    backpointers[pyid] = len(backpointers)
    s = '%s [%s]' % (name, backpointers[pyid])

    # Only print non-empty fields:
    fields = [field for field in api_doc.__dict__.keys()
              if (field in include or
                  (getattr(api_doc, field) is not UNKNOWN
                   and field not in exclude))]
    if include:
        fields = [field for field in dir(api_doc)
                  if field in include]
    else:
        fields = [field for field in api_doc.__dict__.keys()
                  if (getattr(api_doc, field) is not UNKNOWN
                      and field not in exclude)]
    fields.sort()
    
    for field in fields:
        fieldval = getattr(api_doc, field)
        if doublespace: s += '\n |'
        s += '\n +- %s' % field

        if (isinstance(fieldval, types.ListType) and
            len(fieldval)>0 and
            isinstance(fieldval[0], APIDoc)):
            s += _pp_list(api_doc, fieldval, doublespace, depth,
                          exclude, include, backpointers,
                          (field is fields[-1]))
        elif (isinstance(fieldval, types.DictType) and
              len(fieldval)>0 and 
              isinstance(fieldval.values()[0], APIDoc)):
            s += _pp_dict(api_doc, fieldval, doublespace, 
                          depth, exclude, include, backpointers,
                          (field is fields[-1]))
        elif isinstance(fieldval, APIDoc):
            s += _pp_apidoc(api_doc, fieldval, doublespace, depth,
                            exclude, include, backpointers,
                            (field is fields[-1]))
        else:
            s += ' = ' + _pp_val(api_doc, fieldval, doublespace,
                                 depth, exclude, include, backpointers)
                
    return s

def _pp_list(api_doc, items, doublespace, depth, exclude, include,
              backpointers, is_last):
    line1 = (is_last and ' ') or '|'
    s = ''
    for item in items:
        line2 = ((item is items[-1]) and ' ') or '|'
        joiner = '\n %s  %s ' % (line1, line2)
        if doublespace: s += '\n %s  |' % line1
        s += '\n %s  +- ' % line1
        valstr = _pp_val(api_doc, item, doublespace, depth, exclude, include,
                         backpointers)
        s += joiner.join(valstr.split('\n'))
    return s

def _pp_dict(api_doc, dict, doublespace, depth, exclude, include,
              backpointers, is_last):
    items = dict.items()
    items.sort()
    line1 = (is_last and ' ') or '|'
    s = ''
    for item in items:
        line2 = ((item is items[-1]) and ' ') or '|'
        joiner = '\n %s  %s ' % (line1, line2)
        if doublespace: s += '\n %s  |' % line1
        s += '\n %s  +- ' % line1
        valstr = _pp_val(api_doc, item[1], doublespace, depth, exclude,
                         include, backpointers)
        s += joiner.join(('%s => %s' % (item[0], valstr)).split('\n'))
    return s

def _pp_apidoc(api_doc, val, doublespace, depth, exclude, include,
                backpointers, is_last):
    line1 = (is_last and ' ') or '|'
    s = ''
    if doublespace: s += '\n %s  |  ' % line1
    s += '\n %s  +- ' % line1
    joiner = '\n %s    ' % line1
    childstr = pp_apidoc(val, doublespace, depth-1, exclude,
                         include, backpointers)
    return s + joiner.join(childstr.split('\n'))
    
def _pp_val(api_doc, val, doublespace, depth, exclude, include, backpointers):
    from epydoc import markup
    if isinstance(val, APIDoc):
        return pp_apidoc(val, doublespace, depth-1, exclude,
                         include, backpointers)
    elif isinstance(val, markup.ParsedDocstring):
        valrepr = `val.to_plaintext(None)`
        if len(valrepr) < 40: return valrepr
        else: return valrepr[:37]+'...'
    else:
        valrepr = repr(val)
        if len(valrepr) < 40: return valrepr
        else: return valrepr[:37]+'...'