Re: O(n**3) behaviour in reintegrate merge

[Stefan Sperling <st...@elego.de>]

On Thu, Sep 29, 2011 at 11:41:45AM +0200, Stefan Sperling wrote:
> On Wed, Sep 28, 2011 at 01:28:15PM -0400, Paul Burba wrote:
> > I think the far more common use case (based on customer questions I
> > have dealt with) is where a user has been keeping a branch in sync
> > with "trunk" but somewhere along the line did a subtree merge, or is
> > otherwise missing some "reasonably" small part of trunk.  In those
> > cases the error messages pinpoint the problem down the the specific
> > subtree with mergeinfo.
> > 
> > Keep in mind this error has been around since 1.5.5 and I don't see a
> > lot of complaints about it.
> 
> I agree that the error message is useful in the case you describe.
> 
> However, I am not convinced that the approach 1) is smart in general.
> It doesn't matter how common the problematic case is. It does exist,
> and in case people run into it svn is not being helpful. It wastes
> time constructing an error message too large for anyone to read.
> I think that displaying the list of missing ranges should be an
> optional step.

Having reviewed your recent fixes, I took the trunk client for another
spin. First, it manages to generate an error message, which is great.
However, it takes about 3 minutes to do so. Most of this time seems to
be spent downloading the log from the server.
Also, the error message is still *huge*.

So while I think your fixes should be backported to 1.7.1 ASAP,
I don't think the status quo is acceptable. How do we want to move
forward?

For reference, here's the error message I'm getting:


$ time svn merge --reintegrate ^/subversion/branches/fs-successor-ids
subversion/svn/merge-cmd.c:382: (apr_err=195016)
subversion/libsvn_client/merge.c:10879: (apr_err=195016)
subversion/libsvn_client/merge.c:10848: (apr_err=195016)
subversion/libsvn_client/merge.c:10848: (apr_err=195016)
subversion/libsvn_client/merge.c:10786: (apr_err=195016)
svn: E195016: Reintegrate can only be used if revisions 880536 through 1181758 were previously merged from https://svn.apache.org/repos/asf/subversion/trunk to the reintegrate source, but this is not the case:
  subversion/branches/fs-successor-ids
    Missing ranges: /subversion/trunk:880538-880552,880554-880560,880562-880572,880574-880578,880583-880586,880588,880642,880702,880708,880714,880751,880800,880826,880832,880873,880875,880877,880911,880932,880953,881023,881123,881132,881134-881135,881142-881143,881223,881234,881265,881374,881391,881434,881436,881484,881505,881703,881710,881905,881910,881933,881970,882049,882056,882079,882164,882182,882209,882232,882257,882268,882271-882272,882276,882279,882302,882537,882679,882722,882730,882738,882768,882771,882999,883062,883643,883696,883698,883707,883722,883765,883784-883785,883792,883799,883806,883849,883863,883876,883887,883898,883912,883916,884002,884089,884119,884126,884131,884160,884179,884201,884250,884264,884394,884507,884533,884576,884648,884655-884656,884659,884740,884792,884836,884842,884848,884867,884900-884901,884936,884995-884996,885031,885071,885351,885372,885378,885471,885486,885499-885500,885504,885507,885511,885516-885517,885520-885521,885525,885527,885544,885549,885551,885560,885565-885566,885583,885691,885796,885811,885840,885855,886164,886197,886351-886352,886648,886663-886664,886710,886816,886819,886853,886864,886880,886924,887178,887187,887205,887234,887265-887266,887280,887287,887323,887335,887469,887471,887476,887484,887496,887579,887663,887829,887867,887873,887942,887954,888070,888078,888095,888102,888137,888319,888404,888465,888479,888486,888508,888533,888708,888713,888715,888753,888859,888979,889081,889232,889296,889301,889320,889324,889330,889342,889352,889381,889404,889551,889565,889568,889581,889586,889610,889612,889665,889708,889726,889733,889749,889840,890267,890270,890279,890307,890367,890770-890772,890788,890841,890873,890951,891256,891259,891376,891435,891540,891672,891679,891686,891690,891747,891758,892050,892085,892364,892471,892758,892767,892850,892902-892903,893122,893158,893179,893187,893267,893283,893309,893418,893478,893486,893507,893509,893519,893527,893536,893578,894014,894029,894053,894320,895085,895168,895181,895285-895286,895336,895338,895469-895470,895474,895482,895494,895501,895504,895506,895508,895510,895512,895514,895534,895628,895636,895653,895705,895728,895794,896068,896078,896115,896219,896247,896522,896562,896610,896612,896893,896901,896915,897186,897230,897293,897298,897436,897590,898048,898406,898462,898492,898495,898777,898963,899262,899266,899271-899272,899318,899332,899405,899408,899418,899447,899499,899554,899717,899731,899750,899775,899790,899805,899809,899811,899816,899826,899828-899829,900405,900423,900461,900494,900517,900547,900549,900551,900553,900584,900616,900655-900656,900797,900817,900912,900952,900954,900966,900994,901007,901178,901182,901185-901186,901244-901245,901249,901252,901259-901260,901304,901365,901394,901399,901405,901677,901681,901752,901778,901797,901908,901946,901949,902074,902093,902116,902127,902160,902293,902303,902467,902509,902775,902835-902836,902841,902886,903145,903153,903159,903181,903196,903198,903209,903224,903228,903264,903279,903284,903307,903325,903331,903336,903339-903340,903342,903357,903359,903507,903519,903531,903535,903549,903587,903594,903685,903691,903699-903700,903733,903735,903740,903747,903894,903896,903915,903918,903925,904041,904046,904055,904068,904072,904090,904095,904145,904168,904184,904186,904280,904290,904298,904301,904331,904394,904462,904527,904535,904575,904577,904594,904628,904709,904873,904901,904910,904956,904968,904992,905174-905175,905283,905303,905326,905339,905403,905422,905517,905561,905583,905587,905595,905597,905617,905665,905672,905679,905689,905705-905706,905741,905743-905744,905750,905754,905787,905792,905799,905805,905811,905828,905840-905841,905845,905866,905872,905949,905989,906016,906018,906023,906040,906048,906059,906061,906091,906107,906110,906121,906129,906134,906147,906149,906151,906165,906171,906188,906205,906207,906210,906214,906230,906256,906267,906305,906520,906543,906587-906588,906596,906611,906648,906669,906672,906679,906897,906957,907016,907048,907060,907089,907412,907414,907526,907615,907617,907623,907644,907672,907744,907755,907788,907800,907817,907822,907931,907989,908003,908049,908153,908216,908275,908296,908298,908310,908317,908323,908335,908368,908535,908571,908582,908646,908909,908980-908981,909093,909419,909441,909459,909464,909547,909552-909553,909561,909565,909593,909644,909790,909815,909982,910052,910102,910183,910212,910214,910234,910284,910298,910499,910915,911027,911064,911236,911239,911288,911296,911307,911317,911348,911356,911361,911363,911370,911380,911393,911395,911480,911521,911523,911536,911617,911661,911668,911739,911746,911804,911819,911821,911846,911848,911944,911996-911997,912001,912003-912004,912096,912112-912113,912150,912152,912537,915001,915036,915091,915254,915352,915378,915385,915400,915521,915583,915750,915773,915796,915805,915822,915930,915957,915971-915972,915983,916286,916632,916667,916675,916682,916734,916744,916749-916750,916752,916754,916764,916771,916773-916774,916783,916786,916822,916834,916857,916919,917036,917040,917049,917450,917512,917523,917535-917536,917542,917548,917569,917579,917640,917660,917687,917702,917709,917714,917772,917822,917842,917844,917846,917853,917858,917950,917959,918072,918114,918154,918176,918178,918195,918207,918210-918211,918226,918231,918233,918246,918420,918484,918486,918511,918516,918542,918579,918582,918604,918609,918685,918715,918740,918886,918937,918948,918958,918960-918961,918991,919001,919014,919021,919034,919037,919046,919056,919065,919067,919074,919106,919351,919403,919405,919411,919413,919416,919436,919456,919460,919472-919473,919476,919478,919674,919677,919685,919760,919976,919981,919992,919998,920023,920033,920046,920074,920083,920118,920124,920244,920277,920279,920292,920335-920336,920343,920346,920351,920356,920363,920366-920367,920383,920386,920424,920491,920521-920522,920524,920526,920592,920602,920624,920774,920780,920799,920801,920839,920845,920868,920873,920875,920948,920964,920973,920984,920986,921000,921055,921057-921058,921075,921112,921128,921134,921142,921176,921179,921181,921183,921215,921304,921327,921342,921353,921364,921386,921445,921453,921462,921477,921482,921503,921556,921588,921601,921604,921657,921667,921672,921692,921703,921705,921713,921716,921718,921739,921748,921785,921810,921825,921848,921855,921857,921914,921916,921922-921923,921935,921939-921940,921988,922003,922016,922022,922098-922099,922105,922176,922195,922198,922210,922224,922239,922245,922247,922257-922258,922367-922368,922387,922422,922510-922511,922516,922521,922533,922690,922802,922816,922839,922867,922884,922889,922926,922934,922940,923019,923211,923226,923342,923389,923391,923711,923720,923737,923816,923847,923858,923866-923867,923875,923890,923902,923905,923915,924080,924092,924137,924201,924203,924229,924236,924260,924327-924328,924339,924360,924366,924368,924381,924394,924502,924693,924705,924722,924735,924737,924760,924797,924804,924877,924884,924902,924951,924969,924982,924999,925028,925037,925061,925099,925106,925230,925249,925253,925256,925258,925290,925317,925328,925343,925356,925370,925387,925401-925402,925422,925424,925427,925460,925511,925517,925543,925644,925649,925657,925663,925670,925709,925713,926016,926065,926148,926151,926167,926169,926179,926184,926191,926210,926343,926352,926415,926473-926474,926597,926613,926637,926652,926657,926704,926727,926814,926847,926876,926879,926884,926890,927005,927018,927024,927028,927034,927048,927056-927057,927086,927098,927112,927176,927184,927203,927211,927222,927243,927258,927323,927328,927336,927344,927350,927373,927378,927412,927423,927444,927456,927460,927469,927478,927487,927492,927496,927523,927536,927540,927547,927552,927563-927564,927587,927592,927620,927622,927688,927760,927764,927769,927785,927792-927793,927841,927959,928002,928007-928009,928012,928289,928298-928299,928302,928349,928438,928441,928489,928519,928522,928672,928713,928721,928773,928786,928789,928802,928806,928827,928833,928849,928900,928926,928939,928987,929124-929125,929178,929302,929352-929353,929360,929365,929371,929442,929480,929504,929511-929512,929565,929570,929608,929610,929635,929644-929645,929653-929654,929657,929702,929706,929709,929732,929745,929758,929765,929786,929974,930024,930042,930057,930067,930083,930085,930109,930111,930145,930160,930162,930175,930184,930187,930189,930191,930239,930256,930269,930281,930468,930697,930702,930921,930926,930935,930990,931043,931162,931190,931209,931211,931254,931392,931449-931450,931526,931533,931551,931556,931559,931566,931568,931570,931581,931600,931647,931697,931738,931750-931751,931769,931777,931780,931795,931798,931831,931846,931855,931887,931895,931918,931948,931976,931985,932028,932205,932207-932209,932240,932248,932261,932263,932267-932270,932277,932284,932288,932293,932299,932301,932307,932320,932335,932350,932361,932367,932373,932386,932459,932469,932524,932535,932538,932550,932571,932577,932603,932617,932621,932632,932635,932639,932659,932691-932693,932697,932700,932713-932715,932768,932774,932780,932787,932792,932796,932799,932809-932810,932824,932859,932888,932890,932942-932943,933056,933076-933077,933161,933178,933192,933194,933196,933211,933272,933299,933307,933328,933343,933405,933449,933471,933473-933474,933481-933482,933486,933565,933572,933668,933682,933688,933708,933715,933732,933899,933912,933918,933938-933939,933951,933960,933962,933966-933967,933969,933975,933981,933985,933988,934008,934014,934016,934018,934096,934099,934370,934454,934485,934569,934588,934592,934599,934603,934627,934645,934648,934705,934732,934846,934917,934955,934969,934971,934973,934989-934990,935095,935097,935177,935314,935319,935408,935411-935413,935417,935421,935477,935579,935603,935612,935625,935631,935666,935679,935685,935692,935707,935719,935722-935724,935727,935738,935756-935757,935776,935783-935785,935788,935795,935797,935829,935837,935841,935845,935914,935931,935948,935953,935958,935980,935986,935992,935996,936004,936039,936163,936176-936177,936199,936240,936244,936250,936301-936302,936387,936403,936464,936514,936516-936517,936586,936607-936608,936637,936647,936802,936809-936810,936835,936844,936856,936863,936945,936961,936970,936980,937010,937033,937040,937043,937068,937077,937098,937128-937129,937133,937152-937154,937219,937233,937246,937249,937252-937253,937255,937261,937267,937275-937277,937294,937296,937341,937358,937364,937372,937421,937442,937452,937461,937465,937468,937475,937487,937491,937496,937512,937520,937524,937532,937546,937554,937556,937560,937572-937573,937610,937623,937690,937692,937708,937710,937724,937735,937744,937748,937824,938000,938002,938012,938039,938068,938071,938082,938087,938105,938107,938128,938134,938157,938198,938215,938218,938222,938230,938246,938268,938274,938307,938313,938366,938371,938388,938396,938404,938406,938408,938436,938440,938442,938450,938463,938470,938481,938483,938487,938493,938517,938546,938557,938559,938578,938595,938609,938611,938637,938640,938674,938693,938712,938718,938734-938735,938738,938740-938745,938750,938758,938768,938774,938835,938841,938846-938847,938850,938852,938876,938968,938973,938983,938994,938999-939000,939002,939005-939006,939045,939150,939226,939302,939329,939338,939343,939361,939375-939376,939456,939474,939593,939634,939646,939669,939701,939709,939728,940019,940102,940107,940110-940111,940113,940117-940118,940159,940162,940337,940428-940429,940432,940482,940522,940600,940608,940651,940786,940898,940937,940982,941024,941041,941049,941094,941212,941236,941243,941260,941283,941296,941309,941331,941408,941438,941472,941491,941559-941560,941617,941633,941651,941660,941715,941728-941729,941766,941779,941782,941793-941794,941808,941866,941872,941974-941975,942039,942041,942050-942051,942058,942070,942092,942161-942162,942170,942214,942238,942295,942306,942320,942323,942346,942350,942460,942464,942466,942468,942478,942484,942591,942605,942616,942625-942626,942628,942631-942633,942637,942643,942652-942653,942693,942724,942792,942802,942804,942820,942832,942836,942838,942845,942851,942858,942866,942886,942906,942909,942911,942931-942932,942991,943027,943050,943057,943086,943113,943132,943150,943152,943156,943170,943184,943219,943252,943304,943323,943329,943336,943338,943340,943346,943445,943456,943460,943464,943471,943498,943513,943546,943562-943563,943568,943571,943574,943606,943609,943619,943681,943683,943722,943796-943797,943899,943908,943928,943939,943986,944182-944184,944208,944210-944211,944218,944221,944276,944287,944296,944314,944326,944439,944478,944504,944525,944540,944542,944544,944635,944860,944922,944935,944967,944975,944977,944980,944982,945034,945111,945280,945282,945330,945350,945367,945373,945378,945390,945449,945538,945543,945589-945590,945651,945661,945690,945780,945788,945829,945890,945896,945903,945978,946181,946186,946195,946209,946228,946233,946242,946245,946268,946276-946277,946282,946306,946317,946343,946355,946376,946392,946408,946475,946493,946495,946518-946519,946577,946661,946676,946680,946682,946689,946695,946713,946767,946988-946989,946994,946999,947006,947022,947032,947034,947041,947048-947049,947051,947070,947159,947161,947167,947169,947172,947179,947269,947274,947432,947443,947451,947457,947462,947466,947582,947600-947601,947605,947610,947683,947698,947704,947718,947722,947726,947733,947738,947744,947829,947833,947839,947851,947968,947978-947979,947997,948002,948068,948070,948079,948099,948108,948165,948183,948197,948223,948250,948253,948283-948284,948289,948302,948304,948350,948354,948379,948400,948409,948421,948423,948428,948434,948459,948472,948491,948507,948512,948525,948540,948550,948581,948587,948600,948604,948607,948615,948785,948802,948849-948850,948856,948873,948899,948910,948916,948932,948942,948980,949062,949064-949066,949082,949086-949087,949113,949157-949158,949194,949215-949216,949232,949242-949243,949266,949274,949280,949307,949321,949530,949541,949551-949552,949567,949570,949575,949740,949842,949964,950009-950010,950025,950052,950065,950068,950109,950127,950332-950334,950445,950468,950477,950931,950933,950947,951006,951030-951031,951046,951054,951069,951164,951169,951175,951230,951324,951356,951368,951379,951417,951433,951445,951462,951467,951515,951517,951539,951556,951753,951755,951795,951859,951871,951939,952016,952116,952149,952171,952179,952192,952197,952205,952207,952223,952240,952277,952327,952329,952334,952344,952396,952416,952421,952427,952446,952488,952493,952567,952586,952685,952720,952728,952812,952874,952973,952992,953036,953042,953065,953101,953222,953266,953270,953273-953274,953302,953305-953306,953308-953309,953316-953317,953324-953325,953328,953336,953345-953346,953354,953368,953399,953425,953428,953456,953617-953618,953622,953637,953640,953643-953644,953664,953674,953676,953683,953695,953700,953733,953751,953765-953766,953773,953878,953888,953936,953975,953977,953983,953991-953996,954003-954004,954009-954010,954013-954014,954016,954020-954021,954136,954143,954145,954200,954202,954205,954215,954219,954234,954245,954251,954279,954328,954333-954334,954363,954389,954529-954530,954683,954789,954791,954797,954830-954832,954836,954844,954850-954851,954863,954866,954880,954892,954902,955023,955026,955038,955048,955113,955136,955157,955164,955191-955192,955194,955212,955232,955253,955279,955281,955295,955303,955306,955317,955320,955326-955327,955334,955352,955354,955361,955369,955373,955403,955513,955542,955549,955551,955570,955588,955598,955605,955627,955650,955671,955677,955695,955698,955700,955708,955721,955755,955764,955766,955772,955779,955783,955787,955844,955846,955895,955907,955914,955931,955944,955999,956011,956041,956046,956085,956094,956096,956101-956102,956104,956106,956108,956119,956330,956341,956349,956409,956544,956568,956593,956707,956792,956836,956840,956880,956891,956897,956908,956910,956921,956935,956940-956941,957041,957061,957094,957096,957137-957138,957145,957157,957169,957263,957474,957477,957483-957484,957507,957512,957527,957544,957546,957553-957554,957561,957569,957573,957586-957587,957590,957604,957608,957615,957617,957637-957638,957642,957657,957688-957690,957834,957838,957840,957855,957857,957860,957862-957863,957873-957874,957890,957893,957901,957905,957917,957921,957928,957936,957940,957953,957994,958000,958005,958007,958024,958076,958113,958198,958216,958232,958260,958263,958267-958268,958297,958515,958536-958537,958542,958554,958559,958568,958571,958578,958583-958584,958593,958598-958599,958602,958619,958630,958653,958657,958671,958698,958716,958725,958743,958872,958876,958881,958886,958889,958908-958909,958918,958925,958927,958937-958938,958946,958956,958976,958983,958993,959004,959006,959033,959050,959053,959090-959091,959112,959115,959119,959121,959123,959128,959130,959135,959138-959139,959145,959230,959232,959248-959249,959257-959258,959270,959272-959273,959278,959281-959282,959288,959294,959296,959301,959321,959337,959340,959351,959354,959356,959358,959370,959374,959383,959388,959406,959408-959409,959413,959415,959426,959431,959436,959438,959450,959454,959578,959593,959625,959648,959655,959676,959678,959683-959684,959723,959735,959738,959755,959760,959766,959804,959807,959812,959917,959923-959924,959926-959928,959932,959950,959952-959954,959964,959968,959981,959983,959995,959999-960000,960007,960010,960024,960034,960036,960039,960041,960044,960499,960560,960568-960569,960585,960597,960603,960612,960620,960629,960635,960652,960708-960709,960715,960800,960807,960833,960838,960851,960858,960870,960874-960875,960877,960944,960960,960985,960988,961055,961061,961247,961254,961331,961362-961363,961397,961437,961442,961475,961481,961506,961508,961534,961621,961629,961681,961702-961703,961723,961756,961761,961773,961775,961784,961789,961802,961831,961918,961925,961935,961969-961970,962356,962370,962375,962377-962378,962470,962553,962589,962610,962616,962651,962670,962788,962791,962793,962842,962890,962895,962905-962906,962910,963049,963247,963286-963287,963322-963323,963443,963632,963665,963676,963697,963712,963726,963734,963741,963771,963814,963863,963995,964009,964023,964026,964031,964036,964059,964077,964090,964106-964107,964167,964200,964340,964349,964352,964357,964369-964370,964382-964383,964386,964395,964416,964420,964447-964448,964466,964471,964474-964475,964482-964483,964487,964557,964613,964635,964637,964639,964641,964649,964652-964653,964655-964656,964704,964729,964767,964774,964910,964924,964927,964935,964938,964942,964949,964953,964963,965016,965025,965115,965124-965126,965174,965177,965219,965275,965294,965296,965301,965376,965388-965389,965399,965401,965405,965412,965415,965418,965427,965442,965446,965463-965464,965466,965468-965469,965481,965488,965492,965495,965497-965498,965507-965508,965520,965523,965528,965531,965551,965571,965588,965616,965635,965650,965659,965665,965756,965761,965773,965778,965837,965847,965854-965855,965858,965874,965877,965882,965892,965911-965912,965930,965934,965943,966048,966061,966156,966167,966192,966204,966210,966226,966228,966264,966271,966279,966300,966312-966313,966321,966328-966329,966341,966358,966366,966370,966374,966381,966383,966390,966397,966403,966414,966417-966418,966429,966431,966438-966439,966445,966448,966453,966458,966460-966463,966465,966467,966539,966559,966569,966581,966585,966587,966592-966595,966598,966604-966605,966609,966612,966615,966617,966619-966620,966622,966627-966628,966631,966635,966649,966654,966660,966669,966675,966710,966713,966715,966720,966723,966725-966726,966747,966761,966770,966784,966790,966798,966822,966841,966848,966851,966860,966917,966920,966922,967009,967018,967020,967023,967031,967038-967040,967046,967050,967056,967061-967062,967064,967071,967075,967082-967083,967086,967090,967110,967149,967157,967159,967164,967169,967173,967194,967197-967198,967264,978821,978830,978841,978851-978852,978856,978902,979043,979045-979046,979055,979094,979247,979254,979265-979266,979268,979282,979285,979295,979298,979301,979303,979306,979318,979320,979323,979331-979332,979350,979355,979390,979395,979397,979416,979429,979455,979476-979477,979487,979653-979654,979667-979668,979672,979679,979684,979696,979700,979704,979710,979730,979770,979823,979833,979835,979955,979972,979974-979976,980011-980012,980016-980017,980031,980037,980045-980046,980050,980060,980068-980069,980075,980084,980087-980088,980104,980110,980136,980139,980153,980171,980176,980179,980184,980188,980196,980203,980231,980235,980241,980251,980258,980263,980278,980335,980362,980373,980376,980382,980405-980406,980409,980427,980454,980459,980461,980465,980470,980486,980497,980500,980547,980569,980602,980665,980668,980670,980672,980679,980688,980716,980727,980729-980730,980744-980745,980751,980774,980784,980797,980804,980809,980811,980878,980889,980910,980924,981039,981074-981075,981170-981171,981182-981183,981185,981196,981198-981199,981201,981214,981230,981232,981246,981266,981275,981282,981313,981319,981328,981330,981339,981418,981426,981449,981462,981470,981479,981483,981489,981507,981513,981519-981520,981522,981528,981538,981559,981564,981568,981570,981575,981593,981605,981641,981653,981683,981701,981729,981757,981789,981803,981805,981807,981818,981825-981826,981839,981869,981872,981876,981878,981881,981885,981890,981893-981894,981897,981899-981900,981903,981905,981911,981919,981921,981935,981937,981942,981960,981966,981989,981997,982005,982042,982056,982064,982173,982224,982231,982246,982248,982256,982259,982267-982268,982275,982283,982291,982295,982307,982365,982386,982397-982398,982410,982415,982429,982483,982487,982495,982500,982502,982512,982514,982516,982527,982534,982542,982550,982563,982581-982582,982587,982603,982628,982634,982647,982673,982706,982717,982726,982761-982762,982765,982775,982791,982803,982808,982814,982863,982900,982913,982915-982919,982929,982931-982932,982935,982937,982948,982952,982957,982959,982964,982973,982982-982983,983016,983026,983033,983037,983041,983064,983074,983096,983139,983144,983221-983222,983229,983248,983255,983261,983263,983266,983591,983593-983594,983649,983654-983655,983665,983668,983689,983691,983720,983727,983729,983747,983772,983775,983796,983801,983823,983827,983858,983862,983913,983937-983938,983942,983947-983948,983951-983952,983969,983978-983979,984006-984007,984012,984047,984051-984053,984056,984077,984090,984182,984212,984280,984348-984349,984365,984397,984406,984429,984434,984447,984463,984496,984525,984538,984546,984549,984555-984556,984558,984560,984565,984567-984568,984651,984751,984758,984760,984765,984781,984797,984833-984834,984876,984911,984923,984926,984928,984931,984990,985152,985219,985254,985294-985295,985339,985459,985621,985735,985815,985839,985901,985913,985997,986040,986200,986316,986332,986338,986349,986375,986377,986391,986403,986408,986466,986510,986567,986667,986716,986747,986754,986865,986869,987112,987188,987200,987203,987210-987211,987235,987309,987379,987464,987472,987506,987512-987513,987518,987523,987526,987530-987531,987561,987592,987727,987730,987732,987735,987939,987956,988022,988059,988068,988072,988074,988076,988082,988086,988100,988117,988144,988150,988152,988159,988167,988175,988188,988207,988209,988460,988550,988627,988814,988956,988978,989017,989063,989101,989108,989173,989189,989218,989235,989249,989273,989327,989605,989610,989658,989787,989796,989810,989813,989819,989824,989826,989839,989851,989854,989863,989867-989868,989937,990089,990103,990105,990113,990119,990121,990128,990172-990173,990193,990202-990203,990214,990248,990282,990325,990358-990359,990363,990367,990370-990372,990380-990381,990385,990576,990587,990594,990634,990729-990730,990760,990772,990774,990790,990798,990801,990804,990812,990818,990824,990826,990830,990916,990919,990921,990952,990956,991155,991158,991160,991171,991175,991182,991188,991192,991206,991211-991212,991223,991225,991229,991231,991236-991239,991262-991263,991282,991291,991297,991342,991348,991352-991353,991384,991396,991459,991470,991474,991499,991503-991504,991508-991509,991512,991534,991543,991546,991559,991563,991569-991570,991581,991599,991618-991619,991631,991638,991642,991645,991656,991662-991663,991679,991698,991703,991705,991716-991717,991723,991732,991887,991894,991941,991958,991970,991972,992004,992007,992009-992010,992017,992019,992024,992028,992041-992042,992050,992114,992276,992314,992336,992343,992390-992391,992402,992566,992873,992884,992886,992893,992967,992993,992997,993005,993015,993021,993026,993028,993031-993033,993036-993037,993039,993041,993073,993102,993116,993147,993149,993160,993183,993253,993258,993272,993281,993308,993310,993314,993327,993356,993358,993390,993419,993425,993504,994957,995156,995183,995194,995210,995212,995215,995260,995357,995363,995372,995377,995380,995382-995383,995387-995388,995390,995394-995395,995400,995402,995407,995441,995447,995450,995455,995459,995461,995465,995472,995475,995484-995485,995498,995501-995502,995508,995513,995530,995547,995685,995703,995737-995739,995746,995749,995766,995775,995788,995792,995798-995799,995801,995808,995814,995816,995822,995824,995828,995832,995840,995843,995848,995866,995875,995887,995927,995931-995932,995957,995962,995977,995983,995998,996288,996290,996324,996334,996344,996347,996354,996359,996362,996368,996382-996383,996386,996388,996438,996442,996456,996473,996482,996570-996571,996574,996581,996595-996596,996659,996661,996797,996811,996884,996907,996914,997010,997026,997065,997070,997203,997228,997237,997249,997265,997282,997322,997334,997340,997342,997358,997361,997395,997403,997457,997466,997471,997474,997639-997640,997660,997662,997691,997696,997715,997718,997725,997735,997740-997742,997766,997777,997781,997783,997825,997850,997854,997872-997873,997895,997905,997923,998049,998079,998088,998127,998180,998183,998193,998296,998426,998430-998431,998434,998436,998502,998644,998646,998648,998653-998654,998661,998769,998772,998775,998779,998795,998798,998802,998853,998859,998863,998880,998933,998942,998968,998980,999061,999111,999113-999114,999148,999158,999265,999267,999300,999302,999312,999375,999384,999391,999474,999498,999503,999505,999507,999536,999755,999757,999759,999778,999785,999799,999820,999825,999829,999837-999838,999853,999858,999864,999917,999938,999992,1000038-1000039,1000045,1000055,1000057,1000059-1000060,1000063,1000065,1000149,1000230,1000238,1000353,1000370,1000386,1000406,1000461,1000484,1000490,1000495,1000502-1000503,1000518,1000526,1000544-1000545,1000557,1000607,1000612,1000691,1000693,1000816,1000824-1000825,1000874,1000882,1000955,1000982,1001007,1001009,1001063,1001109,1001246,1001277,1001291,1001304,1001309,1001312-1001313,1001321,1001493,1001650,1001655,1001669,1001677-1001678,1001704,1001770,1001811,1001814,1001847,1001872,1002094,1002100,1002141,1002144,1002151,1002184,1002241,1002258,1002260,1002271,1002298,1002313,1002372,1002408,1002466,1002470,1002499,1002502-1002503,1002507,1002568,1002581,1002591,1002610,1002637,1002677,1002719,1002722,1002725,1002735,1002761,1002790,1002793,1002890,1002898,1003029-1003030,1003043,1003064,1003210-1003211,1003213,1003238,1003476,1003482,1003507,1003529,1003546,1003563,1003591,1003603,1003632,1003651,1003924,1003958,1003972,1003986,1003989,1003991,1004209,1004212,1004276,1004280,1004282-1004283,1004286,1004288,1004299,1004306-1004307,1004314,1004321-1004322,1004324,1004348-1004349,1004374,1004383-1004384,1004397,1004418,1004581,1004629,1004644,1004694,1004705,1004710,1004724,1004727,1004746,1004792,1004834,1004883,1004975,1004988,1005008,1005018,1005035,1005040,1005050,1005052-1005053,1005055,1005102,1005104,1005106-1005107,1005173,1005212,1005386,1005388,1005413,1005425-1005426,1005437,1005440,1005444-1005446,1005454,1005543,1005668,1005751,1005754,1005766,1005774,1005783,1005786,1005817,1005819,1005821-1005822,1005824,1005836,1005840,1005853,1005879,1005940,1005985,1021282,1021313,1021402,1021405,1021412,1021416,1021430-1021431,1021477,1021493,1021722,1021741,1021760,1021779,1021783,1021795,1021800,1022059,1022061,1022123,1022132,1022281,1022308,1022433,1022440,1022457,1022466,1022469-1022470,1022474,1022548,1022556,1022588,1022594,1022597,1022660,1022665,1022675,1022692,1022707,1022731,1022744,1022778,1022801,1022861-1022862,1022880,1022885,1022898,1022912,1022931,1022959,1023080,1023104,1023113,1023128,1023339,1023547,1023571,1023589,1023624,1023647,1023658-1023659,1023708,1023740,1023742,1023754-1023755,1023758,1023766,1023836,1023874,1023928,1024187,1024206,1024210,1024269,1024287,1024311,1024319,1024558,1024560,1025481,1025501,1025595,1025600,1025602,1025613,1025622,1025628,1025645,1025662,1025667-1025668,1025754,1025921,1026102,1026105,1026107,1026128,1026143,1026149,1026253,1026270,1026280,1026290,1026293,1026303,1026313,1026320,1026348,1026356,1026367,1026383,1026401,1026408,1026434,1026442,1026444,1026451,1026454,1026461,1026464,1026472,1026475,1026969,1026978,1027029,1027031-1027032,1027040,1027077,1027079,1027081,1027101,1027156,1027168-1027169,1027185,1027192,1027197,1027204-1027205,1027212-1027213,1027216,1027222,1027225,1027231-1027232,1027236-1027237,1027241,1027245,1027247,1027249,1027252-1027253,1027262,1027264-1027265,1027291,1027295,1027313,1027358-1027359,1027428,1027443,1027475,1027576,1027601,1027614,1027624,1027643,1027732,1027751,1027851,1027853,1027896,1027899,1027917,1027920,1027931,1027957,1027970,1028011,1028050,1028084,1028098,1028108,1028120,1028123,1028125,1028152,1028157-1028158,1028169,1028240,1028251,1028253,1028271,1028279,1028289,1028296,1028298,1028307,1028316,1028337,1028340-1028341,1028352,1028358,1028408,1028424,1028472,1028568,1028597,1028613-1028614,1028673,1028742,1028795,1028805,1028809,1028814,1028828,1028830,1028855,1028869,1028883,1029079,1029108-1029109,1029240,1029638,1029655,1029737,1029751,1029760,1029802,1029808,1029811,1029813,1030003,1030010,1030042,1030064,1030079,1030085,1030092,1030095,1030136,1030141,1030148-1030149,1030164,1030207,1030240,1030279,1030289,1030374,1030399,1030407,1030413,1030420,1030439,1030470,1030500-1030501,1030506,1030512,1030522,1030536,1030540,1030557-1030558,1030580,1030596,1030598,1030637,1030651,1030704,1030755,1030872,1030902,1030906,1030909,1030912,1030926,1030934,1030983,1031035,1031052,1031078,1031082,1031114,1031125,1031140,1031160-1031161,1031164-1031165,1031186,1031202,1031206,1031234,1031255,1031259,1031356,1031400,1031411,1031419,1031507,1031514,1031526,1031532,1031610,1031616,1031649,1031654,1032276-1032277,1032279,1032568,1032610,1032657,1032808,1032847,1032992,1033001,1033006,1033028,1033035,1033045,1033062,1033086,1033104,1033107-1033108,1033128,1033146,1033163,1033165-1033166,1033182,1033184,1033198,1033233,1033242,1033248,1033269,1033282,1033290,1033320,1033411,1033455,1033500,1033508,1033531,1033541,1033545,1033547,1033555,1033558,1033566,1033574,1033584,1033597,1033599,1033606,1033622,1033625,1033632,1033646,1033665,1033678,1033685,1033699,1033707,1033709,1033723,1033744,1033760,1033774,1033861-1033862,1033888,1033914,1033917,1033919,1033921,1033924,1033945-1033946,1033983,1034019,1034040,1034060-1034061,1034074-1034075,1034084,1034099,1034103,1034139,1034155,1034175,1034232,1034269,1034313,1034340,1034362-1034363,1034366-1034367,1034375,1034379,1034382,1034411,1034413,1034420,1034432,1034435-1034436,1034443,1034455,1034464,1034476,1034490-1034491,1034495,1034557,1034695,1034756-1034757,1034770,1034775,1034779,1035208,1035243,1035248-1035249,1035273,1035277,1035280,1035293,1035301,1035317,1035339,1035347,1035349,1035367,1035375,1035482,1035580,1035588,1035644,1035669,1035677,1035683,1035691,1035745,1035762-1035763,1035773,1035781,1035792,1035831,1035839,1035894,1036029,1036032,1036037,1036042,1036048,1036067,1036078,1036084,1036087,1036092,1036098,1036127,1036138,1036142,1036144,1036166-1036168,1036306,1036316,1036373,1036383,1036386,1036419,1036422,1036429,1036464,1036468-1036469,1036472,1036478,1036494,1036505,1036519,1036534,1036542,1036546-1036547,1036575,1036598,1036618,1036648,1036770,1036791,1036923,1036925,1036927,1036957,1036978,1037252,1037358,1037662,1037676,1037680,1037714,1037738,1037748,1037762,1037796,1037959,1037974,1037989,1037992,1037996,1037998,1038089,1038097,1038126,1038133,1038163,1038185-1038186,1038297,1038302,1038311-1038312,1038325,1038329,1038338,1038340,1038379,1038477-1038478,1038494,1038544,1038558,1038577,1038588,1038598,1038607-1038608,1038621,1038624,1038640,1038650,1038674,1038677,1038680-1038681,1038692,1038704,1038715,1038759,1038763,1038766,1038788,1038792,1038797,1038801,1038843,1038847,1038860,1038867,1038874,1038999,1039007,1039027,1039029,1039040,1039061,1039065,1039072,1039081,1039085,1039089,1039097,1039105,1039122,1039130,1039134,1039140-1039141,1039154,1039161,1039170,1039174,1039195,1039319,1039334,1039349,1039366,1039388,1039397-1039398,1039424,1039473,1039497,1039808,1040058,1040095,1040115,1040126,1040135-1040136,1040204,1040210,1040221,1040232-1040233,1040237,1040255,1040264,1040327,1040438,1040460,1040469-1040470,1040472,1040474-1040475,1040531,1040535,1040574,1040588,1040619,1040648,1040663,1040811-1040812,1040831-1040832,1040903,1040959,1040962,1041006,1041051,1041056,1041068,1041083,1041102,1041137,1041230,1041293,1041319,1041321,1041336,1041353,1041363,1041368,1041422,1041426,1041438,1041457,1041510,1041568,1041572,1041630,1041633,1041638,1041719,1041773,1041782,1041813,1041839-1041840,1041891,1041900,1041920,1042032,1042294,1042319,1042366,1042434,1042460,1042478-1042479,1042586,1042662,1042673,1042679,1042687,1042734,1042755,1042868,1042892,1042963,1042977,1043007,1043009,1043035,1043120,1043136,1043209,1043360,1043373,1043375,1043380,1043391,1043397,1043408-1043409,1043422,1043427,1043551,1043595,1043895,1043966,1043980,1044016,1044023,1044028,1044040,1044068,1044071,1044095,1044139,1044150,1044170,1044319,1044334,1044363-1044364,1044375,1044384,1044425,1044448,1044466-1044467,1044469,1044473,1044486,1044488,1044513,1044833,1044992,1045164,1045176,1045241,1045303,1045378,1045385,1049057,1049138,1049189,1049306,1049328,1049414,1049417,1049497,1049503,1049510-1049511,1049526,1049557,1049578,1049646,1049652,1049658-1049659,1049665,1049668,1049672,1049819,1049924,1049944,1049948,1049985,1049998,1050001,1050019,1050061-1050062,1050083,1050091,1050158,1050216,1050291,1050300,1050332,1050344,1050359,1050442,1050449,1050515,1050548,1050557,1050650,1050719,1050825,1051059,1051144,1051157,1051164,1051270,1051322,1051331,1051385,1051452,1051459,1051475,1051535,1051558-1051559,1051566,1051574,1051620,1051632,1051638,1051702-1051704,1051713,1051720,1051733,1051744-1051745,1051751,1051760-1051761,1051763,1051775,1051778,1051801,1051804,1051819,1051864,1051875,1051886,1051906,1051931,1051939,1051941,1051945,1051968,1051978,1051988,1052029,1052041,1052068,1052084,1052101,1052151,1052166,1052225,1052254,1052340,1052448,1052451,1052505,1052547,1052817,1052822,1052891,1052903,1053072,1053076,1053130,1053133,1053140,1053165,1053174,1053185,1053189,1053208-1053210,1053233,1053469,1053499,1053577,1053645,1053833,1053915-1053916,1053932,1053937,1053941,1053945,1053953,1053955,1053981,1053984,1053996,1053998,1054001,1054006,1054087,1054089-1054090,1054115,1054133,1054167-1054168,1054229,1054249-1054251,1054254,1054264,1054272-1054273,1054277,1054286,1054320,1054421-1054422,1054503,1054513,1054577,1054579,1054583,1054631,1054660,1054680,1054690,1054701,1054704,1054715,1054721,1054742,1054793,1054798,1054989,1055065-1055066,1055080,1055084,1055092,1055114,1055452,1055460,1055462-1055463,1055472,1055478,1055481,1055484,1055494,1055502,1055568,1055637,1055713,1055908,1055984,1056165,1056376,1056416,1056468,1056480,1056482,1056565,1056601,1056605,1056607,1056728,1056873,1057088,1057409,1057746,1057749,1057754,1057763,1057769-1057772,1057908,1057912,1057915,1057925,1058145,1058150,1058173,1058177,1058213,1058237,1058257,1058266,1058269,1058282,1058294,1058479,1058523,1058560,1058632,1058667,1058690,1058722-1058723,1058800,1058812,1058982,1058987,1058989,1058991,1059040,1059046,1059173,1059178-1059179,1059181,1059317,1059762,1059960,1060051,1060107,1060460,1060836,1060883,1061020,1061328,1061437,1061460,1061464,1062313,1062396,1062916,1062974,1062978,1063320,1063337,1063381,1063413,1063429,1063540,1063572-1063573,1063590,1063592-1063593,1063595,1063597,1063599-1063601,1063605,1063684,1063834,1063851,1063861,1063863-1063864,1063870,1063878,1063946,1064093,1064097,1064117,1064122,1064134,1064145,1064151,1064163,1064168,1064177,1064195,1064198,1064242-1064243,1064258,1064261,1064345,1064436,1064456-1064458,1064467-1064468,1064471,1064627,1064631,1064729,1064731,1064734,1064742,1064750,1064762,1064766,1064777,1064839,1064847,1064948,1064991,1065009-1065010,1065171,1065546,1065683,1065715,1066006,1066019,1066046,1066087,1066094,1066114,1066141,1066143,1066148,1066160,1066174,1066177,1066203,1066228,1066241,1066247,1066249,1066270,1066276,1066278,1066312,1066414,1066421,1066438,1066445,1066447,1066449,1066468,1066471,1066479,1066520,1066540-1066541,1066567,1066604,1066633,1066702,1066709,1066820,1066846,1066848,1066854,1066859,1066894,1066898,1066907,1066917-1066918,1066923-1066924,1066941,1066969,1066993,1067014,1067028,1067036,1067048,1067056,1067096,1067180,1067182,1067186,1067195,1067199,1067201,1067211,1067222,1067231,1067237-1067238,1067273-1067274,1067277,1067282-1067283,1067295,1067380,1067669,1067674-1067675,1067678-1067680,1067687,1067696,1067712,1067714,1067717,1067780,1067800,1067824,1067835,1067839,1067918,1067956-1067957,1067960,1067964,1068000,1068009,1068012,1068029,1068040-1068041,1068091,1068129,1068144,1068165-1068167,1068169,1068181,1068184,1068188,1068212,1068217,1068249,1068256,1068262,1068264,1068411,1068436,1068475-1068478,1068516,1068519-1068520,1068523,1068541-1068542,1068544,1068547,1068566,1068569,1068578,1068584-1068586,1068592,1068594,1068597,1068601,1068605,1068613,1068667,1068676,1068748-1068751,1068754,1068757,1068798,1068802,1068814,1068848,1068863,1068886,1068927,1068977,1068988,1068995,1069001,1069140,1069145,1069149,1069158,1069162,1069329-1069331,1069335,1069399,1069408,1069419,1069437,1069452,1069465,1069519,1069527,1069547,1069558,1069572,1069588,1069591,1069602,1069604,1069652,1069668,1069743,1069789,1069791,1069821,1069946,1069960-1069961,1069963,1069978,1070074,1070113,1070115-1070117,1070121,1070162,1070216,1070220,1070224,1070376-1070377,1070402,1070429,1070441,1070473,1070508,1070510,1070543,1070582,1070629-1070630,1070644,1070684-1070685,1070689,1070788,1070833,1070847,1070861,1070892,1070909,1070912,1070920,1070930,1070969,1070980-1070981,1070983,1070985-1070986,1070990,1071014,1071025,1071029,1071081,1071214,1071228,1071239,1071279,1071283,1071304,1071307,1071357,1071368,1071373,1071602,1071625,1071632-1071633,1071650,1071679,1071707,1071711,1071729,1071736,1071739,1071745,1071750,1071752,1071781,1071784,1071795,1071809,1071961,1072083-1072084,1072242,1072288,1072290,1072299,1072302,1072339,1072343,1072353,1072355,1072360,1072367,1072371,1072406,1072412,1072417,1072419,1072423,1072425,1072429,1072431,1072447,1072501,1072519,1072527-1072528,1072534-1072538,1072544,1072623,1072625,1072629,1072692-1072693,1072695,1072927,1072940,1072953,1072997,1073043,1073093,1073102,1073242,1073247,1073281,1073306,1073325-1073326,1073328,1073332,1073340,1073357,1073366,1073377,1073413,1073418,1073689,1073692,1073749,1073797,1073817,1073821,1073824,1073827,1073831,1073854-1073855,1073862,1073869-1073870,1073905,1073955-1073956,1073965,1073974-1073975,1074032,1074037-1074039,1074068,1074072,1074134,1074167,1074334,1074460-1074461,1074474,1074485,1074488,1074492,1074526,1074553,1074572,1074591,1074598,1074664,1074939,1075240,1075313,1075328,1075802,1075844-1075845,1075869,1075886,1075942,1075946,1075963,1075973,1076006,1076018,1076023,1076089-1076090,1076093-1076096,1076098,1076100,1076161,1076172,1076230,1076234,1076313,1076344,1076403,1076556,1076616-1076617,1076631,1076639,1076645,1076658,1076712,1076715,1076726,1076730,1076732,1076734,1076741,1076752,1076759,1076826-1076827,1076839,1076846,1076848,1076854,1076872,1076903,1077861,1077897,1078008,1078018,1078035,1078037,1078050,1078073,1078110-1078111,1078115,1078147,1078151,1078179-1078180,1078185,1078187,1078256,1078262,1078266,1078269,1078330,1078357,1078366,1078497,1078502,1078506,1078527,1078544,1078768,1078828,1078839,1078884,1078914,1078918,1078934,1078949,1078954,1078960,1078962,1078975,1078990,1078996,1079008,1079017,1079033,1079070,1079089-1079090,1079297,1079310,1079348,1079400-1079401,1079409,1079443,1079450,1079458,1079464,1079508,1079512,1079517,1079531-1079532,1079538,1079544,1079550-1079551,1079554,1079563,1079588-1079589,1079591-1079592,1079594,1079686,1079706,1079754,1079756,1079758-1079759,1079803-1079804,1079828,1079851,1079855-1079856,1079858,1079875,1079897,1079914,1079967,1079983,1080034,1080119,1080172,1080175,1080185,1080192-1080193,1080198,1080234,1080236,1080238,1080245,1080248,1080251,1080253,1080263,1080265,1080268,1080272,1080285,1080294,1080333,1080426,1080489,1080491,1080505,1080529,1080534,1080538,1080541,1080543,1080546,1080552,1080559,1080568,1080582,1080605,1080613,1080635,1080640,1080688,1080708,1080921,1080958,1081082,1081086,1081092,1081097,1081102,1081108,1081114,1081124-1081126,1081130,1081135-1081136,1081141,1081148,1081201,1081255,1081342,1081344,1081384,1081390,1081407,1081412,1081441,1081454,1081461,1081464,1081466,1081484,1081487,1081491,1081510,1081513-1081515,1081528,1081539,1081544-1081545,1081552,1081569,1081576,1081584-1081585,1081604,1081615-1081616,1081619,1081623,1081627-1081628,1081635,1081645,1081687,1081703,1081753,1081774,1081781,1081789,1081797-1081800,1081807-1081808,1081886,1081892,1081906,1082106,1082118,1082131,1082137,1082163,1082182,1082187,1082198,1082251,1082307,1082313,1082317,1082320,1082325,1082327,1082339,1082373,1082422-1082423,1082440,1082443-1082444,1082447,1082449,1082451,1082500,1082505,1082523,1082538,1082541,1082549,1082584,1082591,1082626,1082636,1082639,1082650,1082658,1082665,1082667,1082669,1082674-1082676,1082678,1082681,1082690,1082696,1082699-1082700,1082707,1082786,1082806,1082838,1082845,1082851,1082856,1082869,1082874-1082876,1082947,1082980,1082999,1083805,1083817,1083843,1083896,1083920,1084001,1084099,1084138,1084145,1084147,1084166-1084167,1084173,1084185,1084199,1084278,1084283-1084284,1084312,1084330,1084335,1084575,1084578,1084581,1084602,1084764,1084897,1084911,1084930,1084939,1084942,1084962,1084971,1084978,1085031,1085117,1085140,1085184,1085316,1085364,1085426,1085428,1085432,1085445-1085446,1085454,1085464,1085476,1085523,1085535,1085537,1085545-1085546,1085569,1085601-1085602,1085788,1086018,1086021,1086097-1086098,1086112,1086114,1086192,1086195,1086208,1086218,1086222-1086223,1086245,1086269,1086279,1086283,1086421-1086422,1086438,1086475,1086481,1086489,1086492,1086497,1086531,1086537,1086607,1086707,1086717,1086735,1086748,1086754,1086774,1086825,1086926,1086936,1086983,1087015,1087023,1087131,1087171,1087230,1087258-1087259,1087274,1087279,1087282,1087302,1087321,1087335,1087344,1087365-1087366,1087533,1087635,1087666,1087681,1087777,1087779-1087780,1087784-1087785,1087790,1087823,1087838,1087866,1087881,1087892,1088261,1088265,1088269-1088270,1088275-1088276,1088293,1088312,1088318-1088319,1088321,1088334,1088341-1088342,1088351,1088382,1088409,1088462,1088472,1088476,1088479,1088533,1088547,1088552,1088554,1088567,1088581,1088598,1088602,1088609,1088628,1088637,1088642,1088664,1088673,1088680,1088691,1088721,1088773-1088774,1088786,1088793,1088796,1088798-1088799,1088803-1088804,1088811,1088814-1088815,1088817,1088822,1088828,1088832,1088837,1088839-1088841,1088849,1088871,1088873,1088882,1088884,1088954,1088958,1089009,1089017,1089026,1089028,1089049,1089058,1089096,1089142,1089206,1089223,1089238,1089257,1089279,1089281,1089381,1089386-1089387,1089416,1089418,1089426,1089435,1089449,1089482,1089491,1089524,1089536,1089560,1089592-1089593,1089615,1089621,1089766,1089779,1089786,1089806,1089826,1089828,1089831,1089847,1089856,1089877,1089889,1089892-1089893,1089898,1089903,1090015,1090053,1090058,1090172,1090188-1090189,1090217,1090240,1090248,1090253,1090281,1090288,1090291,1090297,1090313,1090403,1090413,1090424,1090446,1090469,1090685,1090688-1090689,1090699,1090713,1090715-1090716,1090784,1090786-1090788,1090790,1090793,1091068,1091077,1091107,1091110,1091115,1091117,1091121,1091141,1091187,1091190,1091198,1091201,1091207,1091225,1091261-1091262,1091272,1091348-1091349,1091364-1091365,1091367-1091368,1091381-1091382,1091399,1091411,1091438,1091449,1091453,1091470,1091474-1091475,1091483,1091491,1091494-1091495,1091512,1091520,1091524,1091559,1091566,1091573,1091603,1091606,1091611,1091717,1091728,1091733,1091746,1091750,1091786,1091808,1091843,1091882,1091891,1091928,1091933,1092033,1092047,1092049,1092145,1092150,1092223-1092224,1092232,1092239-1092240,1092244,1092254,1092273,1092294,1092299,1092304,1092310,1092327,1092421-1092422,1092436,1092446-1092447,1092456,1092469,1092497,1092502,1092506,1092527,1092530,1092537,1092569,1092571-1092572,1092629,1092639,1092641,1092643-1092644,1092659-1092660,1092664,1092672-1092673,1092684,1092686,1092692,1092708,1092712,1092714,1092718,1092721,1092728,1092732-1092735,1092740,1092744,1092746,1092748,1092751-1092752,1092759,1092783,1092852,1092860,1093930-1093931,1093981-1093983,1093989,1093992,1093996,1094000,1094027,1094039-1094040,1094134-1094135,1094146,1094150,1094152-1094153,1094164,1094175,1094180,1094182-1094183,1094185,1094376,1094443,1094563,1094581,1094588-1094589,1094591,1094594,1094609,1094612,1094615,1094636,1094641,1094653,1094672,1094689,1094692,1094707,1094733,1094735,1094746,1094770,1094779,1094788,1094813-1094814,1094816,1094821,1094834-1094835,1094923,1094997,1095005,1095027-1095028,1095056,1095064,1095069,1095078,1095100,1095118,1095122,1095130,1095142,1095145-1095146,1095148,1095150,1095152,1095154,1095159,1095181,1095194-1095195,1095199,1095214-1095215,1095225,1095232,1095237-1095238,1095313,1095318,1095322,1095328,1095347,1095351,1095353,1095359,1095371,1095384,1095399,1095403,1095422,1095433,1095439,1095446,1095450,1095462,1095468,1095494,1095496,1095499,1095502,1095507,1095509,1095515,1095520,1095534,1095536,1095558,1095598,1095617,1095627-1095628,1095645,1095652,1095654,1095662-1095663,1095704-1095705,1095728-1095729,1095734,1095738,1095742-1095743,1095756,1095777,1095787,1095791,1095793,1095795,1095799,1095801-1095802,1095806,1095808,1095810,1095812-1095815,1095817-1095819,1095822-1095825,1095829,1095834,1095838-1095839,1095844,1095907,1095909-1095910,1095912,1095914-1095915,1095946-1095947,1095971,1095981,1096020,1096047,1096057,1096060,1096068,1096070,1096082,1096089,1096147-1096148,1096150,1096152,1096154,1096156-1096157,1096175,1096246,1096258,1096264,1096266,1096276,1096279,1096281-1096283,1096285,1096288,1096298-1096300,1096306,1096314,1096333,1096342,1096363,1096450,1096460,1096490,1096512,1096519,1096555,1096561-1096562,1096619,1096641,1096706,1096738,1096749,1096754,1096759-1096760,1096769,1096772,1096776-1096777,1096779,1096785-1096786,1096793,1096799,1096802,1096809,1096811,1096815,1096826,1096830,1096832-1096833,1096836,1096841,1096847,1096853,1096866,1096868,1096883,1096921,1096927,1096932-1096934,1096939,1096947,1096965,1096967,1096971,1096973,1096975,1096977,1097039,1097050,1097052,1097099,1097119,1097126,1097168,1097171,1097174,1097188,1097203,1097219,1097231,1097234,1097240,1097250,1097257-1097259,1097401,1097430,1097435,1097437,1097441,1097458-1097459,1097488,1097495-1097498,1097507,1097509,1097531,1097547,1097551,1097556,1097560,1097562,1097567,1097577,1097580,1097582,1097598-1097602,1097608-1097609,1097635,1097718,1097725,1097745,1097748,1097751,1097756,1097760,1097788,1097806,1097810,1097931,1097942-1097943,1097949,1098108-1098110,1098112-1098113,1098115,1098117,1098203-1098211,1098396,1098435,1098442,1098446,1098471,1098479-1098480,1098484,1098506,1098523,1098531,1098533,1098535,1098537,1098542,1098546-1098549,1098555-1098556,1098562-1098564,1098573,1098577,1098580,1098594-1098595,1098605,1098608,1098610,1098637,1098640,1098649,1098651,1098653,1098657,1098689,1098694,1098728-1098729,1098734,1098736,1098743,1098745,1098756,1098761,1098768,1098773,1098776,1098793,1098973,1098985-1098986,1098999,1099012,1099043-1099044,1099049,1099066-1099067,1099073,1099089,1099091,1099094,1099100,1099108-1099109,1099122,1099132,1099135,1099143,1099145,1099149,1099162,1099184,1099193,1099196,1099217-1099218,1099220-1099221,1099233,1099236,1099240-1099241,1099251,1099273,1099275-1099276,1099282,1099290,1099292,1099296,1099298,1099304-1099305,1099383,1099395,1099399,1099404,1099409-1099411,1099419,1099429,1099436,1099439-1099440,1099452-1099453,1099456,1099462-1099464,1099484-1099485,1099487,1099492,1099507,1099530,1099574,1099579,1099581,1099583,1099598,1099604,1099616,1099618,1099631,1099649,1099657,1099660,1099680-1099681,1099683,1099689,1099699,1099734-1099735,1099744,1099746,1099748,1099758,1099764,1099773,1099775-1099776,1099778,1099784,1099798,1099807,1099836,1099863,1099908,1099914,1099940-1099941,1099947,1099955-1099956,1099958-1099959,1099961,1099981,1099984,1099992,1100128,1100152-1100153,1100163,1100169,1100177,1100186,1100213,1100234,1100238,1100244,1100258,1100273,1100276,1100285,1100287,1100292,1100303,1100309,1100316,1100318-1100319,1100321,1100326-1100327,1100338,1100348-1100349,1100351,1100353-1100354,1100359-1100361,1100364,1100367,1100375-1100377,1100380,1100388,1100394,1100405,1100424,1100431,1100453,1100460,1100466,1100520,1100523,1100527,1100536,1100538-1100539,1100542,1100546,1100549-1100551,1100553,1100555-1100556,1100617,1100649,1100658,1100674,1100676-1100677,1100704,1100708,1100712,1100714-1100715,1100721-1100723,1100725-1100727,1100733,1100738,1100742,1100744,1100756,1100758,1100760,1100769,1100788-1100789,1100796,1100830,1100844,1100937,1100941-1100943,1100999,1101028,1101060,1101071,1101086,1101091,1101095,1101100,1101102,1101124,1101126,1101171,1101195-1101196,1101202,1101205,1101219-1101220,1101224,1101226-1101227,1101235,1101246-1101247,1101275,1101278,1101374,1101376,1101427-1101428,1101432,1101438,1101467,1101470,1101473,1101475,1101486,1101492,1101498,1101521,1101565,1101567,1101578,1101580,1101599,1101603,1101616,1101635,1101652,1101684,1101701,1101717,1101719,1101726,1101728,1101730,1101734,1101738,1101781,1101788,1101817,1101823,1101833,1101835-1101836,1101848,1101857,1101863,1101868,1101880,1101913,1101918,1101927,1101957,1101966,1101990,1102021,1102054,1102060,1102064-1102065,1102100,1102121,1102143,1102173,1102178,1102218,1102220,1102226,1102228,1102237-1102238,1102242,1102257,1102264-1102265,1102321,1102325,1102331,1102342,1102353,1102367,1102393,1102398,1102426,1102429,1102441,1102443-1102445,1102449,1102455,1102471,1102502,1102592,1102618-1102619,1102626,1102654,1102662,1102690,1102747,1102750,1102753,1102803,1102837,1102843,1102855,1102862,1102871,1102886,1102888,1102894-1102895,1102900-1102901,1102912,1102915,1102917-1102920,1102985,1103151,1103157,1103177,1103179,1103207,1103257,1103260,1103300,1103316,1103333,1103391,1103413-1103414,1103419,1103422,1103457,1103461-1103462,1103464,1103486,1103490,1103493,1103578-1103579,1103582-1103583,1103586,1103589,1103665,1103671,1103684-1103686,1103689,1103697-1103698,1103704,1103706,1103749,1103751,1103753,1103762,1103765,1103770-1103772,1103838,1104056-1104057,1104072,1104092,1104119,1104122,1104124-1104125,1104156-1104157,1104160,1104165,1104177,1104181,1104184-1104185,1104191-1104192,1104194,1104205,1104208-1104209,1104211,1104218,1104228,1104234,1104236,1104246,1104271,1104275-1104277,1104282,1104284-1104285,1104292,1104301,1104306,1104308-1104309,1104319,1104323,1104332-1104333,1104342,1104349,1104356,1104358,1104378,1104380,1104383,1104387,1104393,1104400,1104408,1104419,1104583,1104610,1104620,1104631,1104641,1124156,1124170,1124172,1124195,1124197,1124199,1124203,1124207,1124254-1124255,1124259,1124264,1124278,1124283,1124296-1124297,1124300,1124306,1124308,1124319,1124325,1124331,1124375,1124380,1124382,1124399,1124402,1124404,1124407,1124414,1124421,1124436,1124469,1124554,1124556,1124599,1124626,1124659,1124677,1124687,1124707,1124709,1124782,1124843,1124903,1124950,1124988,1124991,1125107,1125126,1125130,1125132,1125138,1125143,1125149,1125151,1125153,1125157,1125162,1125164,1125169,1125171,1125177,1125182,1125193,1125199,1125201,1125288,1125291-1125292,1125302,1125304,1125307,1125311-1125313,1125315-1125316,1125326-1125328,1125332,1125338,1125340,1125343,1125351,1125363,1125370,1125379,1125383,1125391,1125398-1125399,1125403,1125409,1125415,1125418,1125426,1125429,1125443,1125450,1125455,1125496,1125498,1125548,1125595,1125647,1125673-1125674,1125676,1125708-1125709,1125713,1125716,1125718,1125722,1125724-1125725,1125728-1125729,1125733,1125758,1125761,1125766,1125768,1125773,1125797,1125814-1125815,1125817,1125821,1125834,1125859-1125860,1125869-1125871,1125983,1125998,1126005,1126007,1126098,1126110-1126111,1126203,1126432,1126437-1126438,1126441,1126444,1126459,1126471-1126472,1126480-1126481,1126525,1126539,1126541-1126542,1126553,1126562,1126574,1126577,1126580,1126626,1126629,1126633,1126643,1126652-1126653,1126655,1126731,1126802,1126808,1126810,1126951-1126952,1126965,1126973,1126980,1126983-1126985,1127008,1127069,1127072,1127134,1127143,1127166,1127170,1127189,1127195,1127198,1127220,1127329,1127332,1127352,1127355,1127430,1127465,1127468,1127475,1127480,1127506,1127518,1127539,1127545,1127568,1127575,1127577,1127587,1127617-1127618,1127646,1127695,1127702,1127705,1127709,1127741,1127834,1127847,1127852-1127853,1127859,1127862,1127864-1127865,1127873,1127876,1127878,1127885,1127889,1127892,1127895,1127897,1127899,1127902,1127904,1127909,1127927,1127930,1127932,1127934,1127938,1127948,1127954,1127958,1127960,1127990,1127992-1127993,1127996,1128010,1128017,1128021,1128029,1128034,1128051,1128055,1128062,1128095,1128138,1128158,1128164,1128179,1128187,1128190,1128197,1128230,1128233,1128250,1128255,1128259,1128282,1128297-1128298,1128303,1128307,1128320,1128328,1128335,1128340,1128359-1128360,1128367,1128375,1128379,1128389,1128409,1128412,1128436,1128441,1128837,1128857,1128861-1128862,1128872,1128881,1128891-1128892,1128896-1128897,1128909,1128921,1128928,1129201,1129222,1129245,1129255,1129286,1129289-1129290,1129301,1129338,1129582-1129583,1129587,1129621,1129634,1129641,1129643,1129652-1129653,1129660,1129662,1129668,1129676,1129686,1129698,1129722,1129761,1129776,1129795,1129802,1129804-1129805,1129810,1129815,1129818,1129858,1129860,1129910,1129915,1129921-1129923,1129925,1129928,1129947,1129955,1129957,1129965-1129966,1129971,1129973,1129977,1129980,1130036,1130059,1130066,1130069,1130105,1130118,1130128,1130165,1130167-1130168,1130184,1130224,1130227,1130282,1130285,1130303,1130334,1130359,1130365,1130380,1130385,1130396,1130408,1130420,1130448,1130490,1130498,1130500,1130509,1130512,1130522-1130523,1130525,1130528,1130538,1130543,1130548,1130559-1130561,1130569,1130581,1130585,1130592,1130598,1130622,1130624,1130637,1130649,1130672,1130679,1130682,1130688,1130690,1130697,1130773,1130788,1130790,1130809,1130818,1130826,1130830-1130831,1130837,1130841,1130947,1130952,1130986-1130987,1131000,1131003,1131006-1131007,1131052,1131086,1131091,1131094-1131096,1131109,1131120,1131128-1131129,1131160,1131284-1131285,1131326,1131383-1131385,1131387,1131389-1131390,1131403,1131406,1131413,1131431,1131433-1131434,1131437-1131438,1131440-1131442,1131479,1131986,1132275,1132334,1132355,1132357,1132369,1132376,1132413,1132430,1132442,1132444-1132445,1132449,1132455,1132460-1132461,1132464,1132495,1132550,1132561,1132567,1132575,1132588,1132593,1132598-1132599,1132622,1132642,1132657,1132669,1132678,1132686,1132693-1132694,1132731,1132735-1132736,1132739-1132740,1132782,1132789,1132796,1132811,1132834,1132840,1132843,1132919,1132924-1132925,1132942,1132948,1132951,1132953-1132954,1132965-1132966,1132968,1132970-1132973,1132986,1133010,1133018,1133027,1133032,1133067,1133084,1133097,1133099,1133139,1133153,1133231,1133233,1133237,1133305,1133329,1133352,1133358,1133361,1133367,1133417-1133418,1133442,1133449,1133461,1133600,1133612,1133614,1133641,1133704,1133712,1133714,1133717,1133729,1133732,1133740,1133765,1133771,1133773,1133780,1133811,1133820,1133854,1133865-1133866,1133868,1133882,1133887,1133910,1133964,1133981,1134004,1134032,1134037,1134071,1134075,1134084,1134219,1134258,1134263,1134278,1134290-1134291,1134294-1134296,1134302,1134305,1134470-1134471,1134473-1134474,1134477,1134480,1134484,1134487-1134489,1134493,1134553,1134564-1134565,1134567,1134607,1134734,1134932,1135000,1135054,1135076-1135077,1135086,1135102,1135110,1135124,1135127,1135151,1135164,1135166,1135172,1135176,1135180,1135210,1135271,1135274,1135331,1135340,1135343,1135350,1135406,1135416,1135466-1135468,1135471,1135481,1135501,1135504,1135530,1135534,1135536,1135560,1135563,1135575,1135584-1135586,1135602,1135623,1135635,1135651,1135655,1135682,1135743,1135885,1135913,1135953,1135982-1135983,1135986-1135987,1135990,1136038,1136063,1136075-1136076,1136084,1136101,1136114,1136116,1136123,1136137,1136143,1136147,1136241,1136243,1136294,1136354,1136374,1136379,1136382,1136428-1136429,1136435,1136457,1136474,1136505,1136512,1136524-1136525,1136530,1136532,1136538,1136542,1136597,1136651,1136655,1136671,1136680-1136681,1136746,1136748,1136777,1136808,1136823,1136838-1136839,1136858,1136864,1136866,1136869,1136874,1136882,1136885,1136891,1136908,1136917,1136931-1136932,1136948-1136949,1136959,1136969,1136973,1136989,1137005,1137106,1137120,1137378,1137455,1137461-1137462,1137468,1137471,1137545,1137613,1137615-1137616,1137660,1137666,1137674,1137676,1137686-1137687,1137694,1137699-1137700,1137716,1137719,1137723,1137727,1137771,1137785,1137790-1137791,1137799,1137808,1137901,1137927,1137933,1137945,1137947,1137967,1137969,1137973,1138037,1138040-1138041,1138043,1138051,1138054,1138060,1138088,1138091-1138093,1138095-1138096,1138109,1138119,1138139,1138171-1138172,1138187,1138369,1138375,1138387,1138399,1138403-1138404,1138410,1138422,1138425,1138458,1138460,1138474,1138481,1138483,1138486,1138489-1138490,1138492,1138516,1138548,1138781,1138830,1138837,1138871,1138881,1138883-1138884,1138891,1138897,1138900,1138902,1138916,1138928,1138960,1138975,1138977,1139008,1139021,1139024,1139038,1139080,1139082,1139086,1139088,1139110-1139111,1139179,1139195,1139198,1139200,1139211,1139217-1139218,1139229,1139231,1139251,1139256-1139257,1139261,1139268,1139275,1139281,1139305,1139318,1139330,1139332,1139345,1139348-1139349,1139355-1139356,1139360,1139364,1139367,1139372,1139374,1139378,1139398,1139410,1139418,1139501-1139502,1139519,1139566,1139573,1139599,1139602,1139604,1139607,1139610,1139678,1139725,1139766,1139806,1139817,1139914,1139930-1139933,1139935-1139938,1139945-1139946,1139971,1139993,1140020,1140025,1140087,1140093,1140110,1140113,1140203,1140208,1140215,1140227,1140236,1140239,1140242,1140248,1140253,1140289,1140302,1140305,1140312,1140331,1140343,1140349,1140388,1140505-1140506,1140512-1140513,1140518,1140524,1140543,1140563,1140566,1140578,1140584,1140588,1140600,1140611,1140617-1140618,1140630,1140667,1140674,1140686,1140729,1140735-1140736,1140779,1140782,1140787,1140789-1140791,1140794,1140798,1140805,1140825,1140833,1140840,1140847,1140861,1141133,1141291-1141292,1141573,1141582,1141600,1141611,1141639,1141695,1141699,1141704,1141845,1141869,1141883,1141893,1141953,1141962,1141981,1141995,1142028,1142038,1142059,1142065,1142088,1142091,1142098,1142207,1142211-1142212,1142216,1142315,1142413-1142414,1142604,1142652,1142663,1142695,1142701,1142709,1142712,1142717,1142873,1142876,1142966,1142973,1142981,1142998,1143037,1143071,1143085,1143089,1143092,1143103,1143108,1143140,1143143,1143156,1143179,1143348,1143357-1143358,1143369,1143377,1143712-1143713,1143726,1143731-1143732,1143736,1143741-1143742,1143765,1143778,1143826,1143829,1143860,1143880-1143881,1143896,1143899,1143926,1144023,1144120,1144211,1144214,1144216-1144217,1144234,1144279,1144309,1144311,1144315-1144316,1144344,1144381,1144396-1144397,1144413,1144424,1144431,1144474,1144488,1144494,1144502,1144522,1144524,1144528,1144530,1144550,1144563,1144572,1144714,1144717,1144869,1145202-1145203,1145214,1145230-1145231,1145234,1145269,1145386,1145403,1145455,1145478,1145504-1145505,1145508,1145511,1145515,1145519,1145526,1145538,1145572,1145606,1145612,1145637,1145639,1145642-1145643,1145646,1145651,1145653,1145664-1145666,1145670,1145705,1145707-1145708,1145712,1145716,1145765,1145771-1145774,1145792,1145798,1145805,1145852,1145901,1145956,1145963-1145964,1145972,1145982,1145999,1146013,1146032,1146074,1146105,1146112,1146119,1146121,1146131,1146134-1146135,1146140,1146143,1146149,1146153,1146165,1146214,1146219,1146222,1146225-1146226,1146228,1146251,1146274,1146381,1146492,1146496,1146501,1146507,1146510-1146512,1146525,1146528,1146534,1146555,1146606,1146620,1146684,1146690,1146716,1146723,1146762,1146765,1146770,1146781,1146811,1146824,1146826-1146827,1146832,1146834,1146870,1146899,1146904,1146938,1146981-1146982,1147056,1147160,1147293,1147299,1147309,1147538,1147540-1147541,1147584-1147585,1147588-1147589,1147591,1147594,1147596,1147600,1147670,1147882,1148043,1148071,1148083,1148094,1148131,1148134,1148374,1148395,1148424,1148426,1148434,1148436,1148448,1148453,1148502,1148512,1148536,1148566,1148573,1148576,1148588,1148593,1148619,1148629,1148644,1148652,1148662,1148699,1148830-1148831,1148853,1148877,1148882,1148884,1148904,1148907,1148909,1148918,1148923-1148924,1148932,1148934,1148936,1148944-1148945,1148992,1149001,1149010,1149103,1149105,1149135,1149137,1149141,1149151,1149160,1149197,1149210,1149228,1149240,1149264,1149308,1149310,1149312,1149343,1149371-1149372,1149377,1149398,1149401,1149404,1149453-1149454,1149456-1149458,1149460,1149475,1149519,1149533,1149539,1149543,1149546,1149557,1149572,1149612,1149626-1149627,1149671,1149675,1149701,1149713,1149717,1150060,1150073,1150099,1150242,1150246,1150254-1150255,1150257,1150260-1150261,1150266,1150302,1150327,1150344,1150368,1150372,1150439,1150441,1150454,1150459,1150469,1150506,1150783,1150789,1150793,1150801,1150803,1150807,1150812,1150821,1150833,1150841-1150842,1150853,1150867-1150870,1150872-1150875,1150883-1150884,1150924,1150950,1150952,1150954,1150958,1150961,1151015,1151020,1151036,1151044,1151053,1151055,1151068-1151069,1151073,1151166,1151177,1151239,1151244,1151247,1151254,1151260,1151270,1151296,1151590,1151610,1151667,1151672,1151680,1151780,1151824,1151854,1151873,1151904,1151906,1151911,1151916,1151927,1151939,1151948,1151951,1151954,1151957,1151962,1152023,1152026,1152035,1152115,1152117,1152129,1152140,1152142,1152153,1152189-1152190,1152204,1152245-1152246,1152267,1152282,1152286,1152293-1152294,1152297,1152300,1152324,1152326,1152332,1152341,1152345,1152348,1152358,1152360,1152364,1152368,1152410,1152436,1152447,1152449,1152726,1152807,1152809,1152859,1152889,1153106,1153110,1153138,1153141,1153149,1153180,1153414,1153416,1153458,1153486,1153527,1153539-1153540,1153566,1153599,1153618,1153799,1153807,1153839,1153968,1154009,1154023,1154060,1154070,1154115,1154119,1154121,1154144,1154155,1154159,1154165,1154215,1154225,1154273,1154278,1154379,1154382,1154388,1154461,1154598,1154700,1154717-1154718,1154733,1154908,1154913,1154938,1154946,1154948,1154968,1154976,1154982,1155000-1155001,1155015,1155044,1155124,1155131,1155160,1155279,1155313,1155325,1155334,1155391,1155404,1156076,1156080,1156085,1156098,1156173,1156211,1156216,1156218,1156281,1156312,1156434,1156527,1156717,1156721,1156750,1156756,1156764,1156826-1156827,1156838,1156929,1156949,1156953,1157172,1157180,1157244,1157246,1157263,1157292,1157389,1157416,1157537,1157681-1157682,1157700,1157754,1157788,1157906,1157911-1157912,1158166,1158174,1158187,1158193-1158194,1158196,1158201,1158207,1158209-1158210,1158217,1158224,1158285,1158288,1158300,1158303,1158309,1158343,1158358,1158366,1158407,1158419,1158421,1158429,1158436,1158455,1158485,1158491-1158492,1158616-1158617,1158619,1158634,1158854,1158875,1158886,1158893,1158896,1158919,1158923-1158924,1158929,1158936,1158963,1158970,1158979,1158981,1159093,1159098,1159101,1159113-1159114,1159122,1159132,1159136,1159148,1159199-1159200,1159228,1159230,1159275,1159286,1159299,1159359,1159362,1159367,1159400,1159403,1159672,1159686,1159716,1159741,1159751,1159760,1159772,1159775,1159873,1159880,1159924,1160204,1160210,1160212,1160215,1160217,1160318-1160320,1160329,1160601,1160604-1160605,1160615,1160625,1160630,1160645,1160671-1160672,1160682,1160691,1160704-1160705,1160756,1160856,1160875,1161046,1161051,1161063,1161080,1161084,1161131,1161159,1161166,1161184-1161185,1161202,1161210,1161219,1161224-1161225,1161316-1161318,1161467,1161470,1161474,1161589,1161683,1161710,1161721,1162024,1162033,1162040,1162046,1162054,1162065,1162136,1162197,1162201,1162516,1162794,1162880,1162974,1162995,1163151,1163169-1163170,1163173,1163175,1163238,1163243,1163261-1163262,1163296,1163372,1163383,1163393,1163433,1163438,1163557,1163672,1163698,1163704,1163707,1163711,1163722,1163792,1163894,1163903,1163953,1163955,1164027,1164059,1164116,1164165,1164386,1164426,1164517,1164535,1164554,1164556,1164580,1164614,1164645-1164646,1164665,1164760,1164765,1164780-1164781,1164929,1165275,1165316,1165346,1165631,1165713,1165742,1165787,1165791,1165807,1165814,1165819,1166096,1166098,1166101,1166111,1166114,1166158,1166183,1166192,1166229-1166230,1166267,1166298,1166332,1166379,1166481,1166500,1166503,1166510,1166518,1166555,1166596,1166678,1166695,1166705,1166719,1166729,1166732,1166748,1166878,1166900,1167031,1167033,1167062,1167090,1167109,1167123,1167150,1167168,1167173,1167197,1167209,1167228,1167269,1167304,1167306,1167461,1167483,1167503,1167542

    3m2.57s real     0m8.66s user     0m0.49s system
$

Re: O(n**3) behaviour in reintegrate merge

[Daniel Shahaf <d....@daniel.shahaf.name>]

Stefan Sperling wrote on Wed, Oct 12, 2011 at 11:54:44 +0200:
> On Tue, Oct 11, 2011 at 11:21:16AM -0700, Paul Burba wrote:
> > On Tue, Oct 11, 2011 at 6:36 AM, Stefan Sperling <st...@elego.de> wrote:
> > > On Tue, Oct 11, 2011 at 03:05:11PM +0200, Stefan Sperling wrote:
> > >> So while I think your fixes should be backported to 1.7.1 ASAP,
> > >> I don't think the status quo is acceptable. How do we want to move
> > >> forward?
> > >>
> > >> For reference, here's the error message I'm getting:
> > 
> > Hi Stefan,
> > 
> > Yes, the error message is rather long.  But as I've already said, this
> > reintegrate merge is a complete and total abuse of the reintegrate
> > feature.  I'm not sure we can save every user from themselves if they
> > insist on doing strange things....but I've already made that point,
> > and it appears I'm in the minority, so I wont belabor it any further
> > :-)
> 
> I don't agree with this. I wouldn't call it "abuse" of this feature.
> 
> The user is clearly intending to reintegrate the branch. But one of the
> preconditions for reintegration isn't met. Much like trying to merge into
> a mixed-revision working copy, or a working copy with local modifications.
> Would you also call that "abuse"? I doubt that :)
> 

The user simply recalled that 'merge --reintegrate' was the invocation
for folding feature branches back into their parent.  (And when I say
"recalled", I mean "read it off a Subversion Cheatsheet taped to his
monitor".)

> The user error is definitely not on purpose, and I don't see a point
> in punishing users for this error by stealing 3 or more minutes of
> their time gathering information of little value to them.
> Note that the user performing the reintegrate merge is not necessarily
> the same person who performed the cherry-picking merge which makes
> --reintegrate impossible. They might simply be unaware of what happened.

Re: O(n**3) behaviour in reintegrate merge

[Paul Burba <pt...@gmail.com>]

On Wed, Oct 12, 2011 at 5:54 AM, Stefan Sperling <st...@elego.de> wrote:
> On Tue, Oct 11, 2011 at 11:21:16AM -0700, Paul Burba wrote:
>> On Tue, Oct 11, 2011 at 6:36 AM, Stefan Sperling <st...@elego.de> wrote:
>> > On Tue, Oct 11, 2011 at 03:05:11PM +0200, Stefan Sperling wrote:
>> >> So while I think your fixes should be backported to 1.7.1 ASAP,
>> >> I don't think the status quo is acceptable. How do we want to move
>> >> forward?
>> >>
>> >> For reference, here's the error message I'm getting:
>>
>> Hi Stefan,
>>
>> Yes, the error message is rather long.  But as I've already said, this
>> reintegrate merge is a complete and total abuse of the reintegrate
>> feature.  I'm not sure we can save every user from themselves if they
>> insist on doing strange things....but I've already made that point,
>> and it appears I'm in the minority, so I wont belabor it any further
>> :-)
>
> I don't agree with this. I wouldn't call it "abuse" of this feature.
>
> The user is clearly intending to reintegrate the branch. But one of the
> preconditions for reintegration isn't met. Much like trying to merge into
> a mixed-revision working copy, or a working copy with local modifications.
> Would you also call that "abuse"? I doubt that :)
>
> The user error is definitely not on purpose, and I don't see a point
> in punishing users for this error by stealing 3 or more minutes of
> their time gathering information of little value to them.
> Note that the user performing the reintegrate merge is not necessarily
> the same person who performed the cherry-picking merge which makes
> --reintegrate impossible. They might simply be unaware of what happened.
>
>> So while I'm a weak -0 on the basic premise of your patch[1], I won't
>> object to it.
>>
>> Paul
>>
>> [1] Re your present patch, the error message is created such that it
>> appears we have to sync the source branch (/fs-successor-ids) up to
>> HEAD:
>
>> But we need only catch up the branch to to youngest sync from trunk
>> (r1167546) for the reintegrate to be successful:
>
> Right. That should be fixed by printing the last revision of the last
> range which has already been merged.
>
> Of course, the patch isn't finished as it is. I just wanted to see how
> much of a difference it would make to stop downloading the log immediately
> when one missing operative revision was found.
>
> How about we meet in the middle?
> We could have the log message callback keep track of the number of
> missing operative revisions it found, and return
> SVN_ERR_CLIENT_NOT_READY_TO_MERGE if a certain limit is exceeded.
> In which case the error will end with " (one or more additional missing
> revisions not shown, for brevity)".
> Let's say we set the limit to a maximum of 42 missing operative revisions.
> Because 42 is the answer to life, the universe, and everything,
> and because this amount of missing revivions should fit well into the use
> case you have in mind, where only a few revisions are missing and the
> user would like to see them all at once without running the 'svn
> mergeinfo' command. What do you think?

Hi Stefan,

Your proposition is a good compromise.  It saves users in your use
case from a lengthy wait for a ginormous (and largely useless) error
message but preserves the current benefits for the more common(?) use
case where only a few revs are missing.

42 as the limit?  Why not, it's manageable.  One question though, were
you thinking that 42 is the limit for *all* subtrees and if the first
time that limit is exceeded we stop?  Or per subtree?

What I mean by this is when the reintegrate source's subtree mergeinfo
doesn't reflect that it is synced with the reintegrate target.  Recall
that in that case the error breaks out the missing ranges by subtree.
For example, say we tried something dubious like reintegrating the
1.7.x branch to trunk:

C:\SVN\src-trunk-2>svn merge ^^/subversion/branches/1.7.x
C:\SVN\src-trunk-2 --reintegrate
..\..\..\subversion\svn\merge-cmd.c:382: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10861: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10830: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10830: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10768: (apr_err=195016)
svn: E195016: Reintegrate can only be used if revisions 1145993
through 1185721 were previously merged from
https://svn.apache.org/repos/asf/subversion/trunk to
 the reintegrate source, but this is not the case:
  subversion/branches/1.7.x
    Missing ranges:
/subversion/trunk:1145999,1146032,1146074,1146105,1146112,1146119,1146131,1146134-1146135,1146140,1146143,1146149,1146153,1146165,1146214,11
46225-1146226,1146228,1146251,1146381,1146496,1146501,1146507,1146510-1146512,1146525,1146528,1146534,1146690,1146716,1146723,1146762,1146765,1146770,1146811,11
46824,1146826-1146827,1146938,1146981-1146982,1147056,1147160,1147538,1147540-1147541,1147584-1147585,1147588-1147589,1147591,1147594,1147596,1147600,1147670,11
48043,1148134,1148395,1148426,1148434,1148436,1148448,1148453,1148502,1148512,1148536,1148573,1148576,1148593,1148619,1148629,1148644,1148830-1148831,1148884,11
48904,1148907,1148909,1148918,1148923,1148932,1148934,1148944-1148945,1148992,1149001,1149010,1149103,1149135,1149137,1149151,1149197,1149210,1149264,1149310,11
49312,1149404,1149453-1149454,1149456-1149458,1149460,1149475,1149519,1149533,1149543,1149546,1149557,1149612,1149626,1149671,1149717,1150060,1150073,1150099,11
50246,1150255,1150257,1150344,1150439,1150454,1150459,1150469,1150783,1150789,1150793,1150801,1150803,1150807,1150821,1150833,1150841-1150842,1150867-1150870,11
50872-1150875,1150883-1150884,1150924,1150950,1150952,1150954,1150958,1150961,1151015,1151020,1151044,1151053,1151055,1151068-1151069,1151073,1151166,1151239,11
51244,1151247,1151254,1151260,1151270,1151296,1151590,1151667,1151672,1151680,1151780,1151824,1151873,1151904,1151916,1151927,1151939,1151948,1151951,1151954,11
51957,1151962,1152023,1152026,1152035,1152115,1152117,1152142,1152153,1152204,1152245-1152246,1152293-1152294,1152297,1152300,1152324,1152326,1152332,1152341,11
52345,1152348,1152358,1152360,1152364,1152368,1152410,1152436,1152447,1152449,1152807,1152859,1152889,1153106,1153110,1153149,1153180,1153414,1153458,1153486,11
53527,1153539,1153599,1153618,1153839,1154060,1154070,1154388,1154598,1154700,1154913,1154938,1154946,1154948,1154968,1154976,1155000-1155001,1155279,1155325,11
56076,1156080,1156173,1156211,1156281,1156434,1156756,1156764,1156826,1156929,1156949,1156953,1157172,1157180,1157244,1157246,1157263,1157292,1157389,1157537,11
57681-1157682,1157700,1157754,1157788,1157906,1157911-1157912,1158166,1158174,1158224,1158300,1158343,1158358,1158366,1158429,1158485,1158491-1158492,1158923,11
58929,1158936,1158970,1158979,1158981,1159113-1159114,1159122,1159199-1159200,1159228,1159286,1159299,1159359,1159362,1159367,1159403,1159672,1159716,1159741,11
59751,1159775,1159873,1159880,1159924,1160204,1160210,1160212,1160215,1160217,1160318-1160320,1160601,1160604,1160615,1160625,1160630,1160645,1160672,1160691,11
60856,1160875,1161046,1161051,1161084,1161131,1161159,1161166,1161184,1161202,1161219,1161224-1161225,1161316-1161318,1161467,1161470,1161474,1161589,1161710,11
62040,1162046,1162054,1162065,1162136,1162197,1162794,1163151,1163169-1163170,1163173,1163175,1163238,1163243,1163296,1163372,1163383,1163393,1163433,1163438,11
63672,1163698,1163704,1163707,1163711,1163894,1163903,1163955,1164059,1164116,1164165,1164426,1164556,1164614,1164646,1164665,1164780-1164781,1164929,1165275,11
65316,1165346,1165631,1165713,1165742,1165787,1165791,1165807,1165814,1165819,1166096,1166098,1166101,1166111,1166114,1166158,1166183,1166192,1166229-1166230,11
66267,1166298,1166332,1166481,1166503,1166510,1166518,1166596,1166695,1166705,1166719,1166729,1166732,1166748,1166878,1166900,1167031,1167033,1167090,1167109,11
67123,1167150,1167168,1167197,1167228,1167304,1167306,1167461,1167483,1167542,1167546,1167616,1167681-1167682,1169717,1169755,1169770,1169799,1169806,1169837,11
69851,1169939,1169947,1169970,1170120,1170126,1170155,1170159,1170183,1170198,1170205,1170324,1170327,1170329,1170472,1170836,1170838,1170843,1170863,1170868,11
70915,1170919,1170924,1171000,1171196,1171351,1171353,1171358,1171702,1171713,1171732,1172391,1172400,1172407,1172411,1172512,1172527,1172548,1172582,1172586,11
72602,1172604,1172609,1172652,1172672,1172675,1172685,1172692,1172773,1173095,1173112,1173126,1173129,1173137,1173153,1173162,1173170,1173191,1173216,1173224,11
73235,1173238,1173240,1173271,1173574,1173642,1173667,1173750-1173751,1173759,1173807,1173809,1173935,1173942,1173992,1174039,1174041,1174043-1174044,1174046,11
74054,1174068,1174074,1174111,1174132,1174139,1174145,1174149,1174156,1174163,1174166,1174265,1174342,1174352,1174355,1174388,1174526,1174582,1174612,1174693,11
74699,1175068,1175835,1175849,1175903,1175938,1176416,1176797,1176894-1176896,1176904,1176909,1177494,1177563,1177693,1177700,1177702,1177732,1178265,1178280,11
78282,1178415,1178435,1178831,1178846,1178910,1178942,1179117,1179136,1179157,1179295,1179297,1179299-1179300,1179312,1179323,1179430,1179545,1179675,1179776,11
80154,1180628,1180724,1180771,1180868,1181090,1181110,1181215,1181232-1181233,1181326,1181609,1181676,1181721,1181727,1181800,1181849,1181853,1181857-1181858,11
81862-1181863,1181869-1181870,1182054,1182104,1182108,1182112-1182113,1182118,1182120,1182123,1182125-1182126,1182128,1182130,1182135,1182138,1182269,1182340,11
82373-1182374,1182376,1182396,1182435,1182459,1182467-1182468,1182475,1182492,1182496-1182497,1182499,1182513,1182527,1182679,1182771,1182778,1182784,1182790,11
82975,1182979,1182983-1182985,1182988,1183174
  subversion/branches/1.7.x/CHANGES
    Missing ranges: /subversion/trunk/CHANGES:1182385
  subversion/branches/1.7.x/subversion/include/private/svn_adler32.h
    Missing ranges:
/subversion/trunk/subversion/include/private/svn_adler32.h:1146149
  subversion/branches/1.7.x/subversion/include/private/svn_string_private.h
    Missing ranges:
/subversion/trunk/subversion/include/private/svn_string_private.h:1146149
  subversion/branches/1.7.x/subversion/include/private/svn_temp_serializer.h
    Missing ranges:
/subversion/trunk/subversion/include/private/svn_temp_serializer.h:1146149
  subversion/branches/1.7.x/subversion/libsvn_fs_fs/temp_serializer.c
    Missing ranges:
/subversion/trunk/subversion/libsvn_fs_fs/temp_serializer.c:1146149
  subversion/branches/1.7.x/subversion/libsvn_fs_fs/temp_serializer.h
    Missing ranges:
/subversion/trunk/subversion/libsvn_fs_fs/temp_serializer.h:1146149
  subversion/branches/1.7.x/subversion/libsvn_subr/adler32.c
    Missing ranges: /subversion/trunk/subversion/libsvn_subr/adler32.c:1146149
  subversion/branches/1.7.x/subversion/libsvn_subr/hash.c
    Missing ranges: /subversion/trunk/subversion/libsvn_subr/hash.c:1146149
  subversion/branches/1.7.x/subversion/libsvn_subr/svn_temp_serializer.c
    Missing ranges:
/subversion/trunk/subversion/libsvn_subr/svn_temp_serializer.c:1146149
  subversion/branches/1.7.x/subversion/tests/cmdline/basic_tests.py
    Missing ranges:
/subversion/trunk/subversion/tests/cmdline/basic_tests.py:1171732

Would the rev limit apply separately to each subtree?

Paul

P.S. Sorry about the tardy reply, I was on the road last week, saw
this, flagged it, and promptly forgot about it :-\

> In my patch, the current limit is 1. It would be easy to extend this to
> 42 (or some other value) and adjust the error message accordingly.
>

Re: O(n**3) behaviour in reintegrate merge

[Stefan Sperling <st...@elego.de>]

On Tue, Oct 11, 2011 at 11:21:16AM -0700, Paul Burba wrote:
> On Tue, Oct 11, 2011 at 6:36 AM, Stefan Sperling <st...@elego.de> wrote:
> > On Tue, Oct 11, 2011 at 03:05:11PM +0200, Stefan Sperling wrote:
> >> So while I think your fixes should be backported to 1.7.1 ASAP,
> >> I don't think the status quo is acceptable. How do we want to move
> >> forward?
> >>
> >> For reference, here's the error message I'm getting:
> 
> Hi Stefan,
> 
> Yes, the error message is rather long.  But as I've already said, this
> reintegrate merge is a complete and total abuse of the reintegrate
> feature.  I'm not sure we can save every user from themselves if they
> insist on doing strange things....but I've already made that point,
> and it appears I'm in the minority, so I wont belabor it any further
> :-)

I don't agree with this. I wouldn't call it "abuse" of this feature.

The user is clearly intending to reintegrate the branch. But one of the
preconditions for reintegration isn't met. Much like trying to merge into
a mixed-revision working copy, or a working copy with local modifications.
Would you also call that "abuse"? I doubt that :)

The user error is definitely not on purpose, and I don't see a point
in punishing users for this error by stealing 3 or more minutes of
their time gathering information of little value to them.
Note that the user performing the reintegrate merge is not necessarily
the same person who performed the cherry-picking merge which makes
--reintegrate impossible. They might simply be unaware of what happened.

> So while I'm a weak -0 on the basic premise of your patch[1], I won't
> object to it.
> 
> Paul
> 
> [1] Re your present patch, the error message is created such that it
> appears we have to sync the source branch (/fs-successor-ids) up to
> HEAD:

> But we need only catch up the branch to to youngest sync from trunk
> (r1167546) for the reintegrate to be successful:

Right. That should be fixed by printing the last revision of the last
range which has already been merged.

Of course, the patch isn't finished as it is. I just wanted to see how
much of a difference it would make to stop downloading the log immediately
when one missing operative revision was found.

How about we meet in the middle?
We could have the log message callback keep track of the number of
missing operative revisions it found, and return
SVN_ERR_CLIENT_NOT_READY_TO_MERGE if a certain limit is exceeded.
In which case the error will end with " (one or more additional missing
revisions not shown, for brevity)".
Let's say we set the limit to a maximum of 42 missing operative revisions.
Because 42 is the answer to life, the universe, and everything,
and because this amount of missing revivions should fit well into the use
case you have in mind, where only a few revisions are missing and the
user would like to see them all at once without running the 'svn
mergeinfo' command. What do you think?
In my patch, the current limit is 1. It would be easy to extend this to
42 (or some other value) and adjust the error message accordingly.

Re: O(n**3) behaviour in reintegrate merge

[Paul Burba <pt...@gmail.com>]

On Tue, Oct 11, 2011 at 6:36 AM, Stefan Sperling <st...@elego.de> wrote:
> On Tue, Oct 11, 2011 at 03:05:11PM +0200, Stefan Sperling wrote:
>> So while I think your fixes should be backported to 1.7.1 ASAP,
>> I don't think the status quo is acceptable. How do we want to move
>> forward?
>>
>> For reference, here's the error message I'm getting:

Hi Stefan,

Yes, the error message is rather long.  But as I've already said, this
reintegrate merge is a complete and total abuse of the reintegrate
feature.  I'm not sure we can save every user from themselves if they
insist on doing strange things....but I've already made that point,
and it appears I'm in the minority, so I wont belabor it any further
:-)

So while I'm a weak -0 on the basic premise of your patch[1], I won't
object to it.

Paul

[1] Re your present patch, the error message is created such that it
appears we have to sync the source branch (/fs-successor-ids) up to
HEAD:

C:\SVN\src-trunk-3>svn up
Updating '.':
At revision 1181989.

C:\SVN\src-trunk-3>svn merge
https://svn.apache.org/repos/asf/subversion/branches/fs-successor-ids
. --reintegrate
..\..\..\subversion\svn\merge-cmd.c:382: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10918: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10887: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10887: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10834: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10834: (apr_err=195016)
svn: E195016: Reintegrate can only be used if revisions 880536 through
1181989 were previously merged from
https://svn.apache.org/repos/asf/subversion/trunk to the reintegrate
source, but this is not the case.

..\..\..\subversion\libsvn_client\merge.c:10064: (apr_err=195016)
..\..\..\subversion\libsvn_ra_neon\log.c:532: (apr_err=195016)
..\..\..\subversion\libsvn_ra_neon\util.c:1323: (apr_err=195016)
..\..\..\subversion\libsvn_ra_neon\util.c:1556: (apr_err=195016)
..\..\..\subversion\libsvn_ra_neon\log.c:321: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:9865: (apr_err=195016)
svn: E195016: Working copy and merge source not ready for reintegration

But we need only catch up the branch to to youngest sync from trunk
(r1167546) for the reintegrate to be successful:


---trunk@880535------------------------------>
        |                         |
       copy                   cherrypick
        |                       merge
        |                      r1167546
        |                         |
        V                         V
   fs-successor-ids@880536-----r1167550------->

> Just to drive my point home, compare to this, which is what I get
> with the patch below (I don't intend to commit this as it is, and
> certainly not before this discussion has been resolved).
>
> $ time svn merge --reintegrate ^/subversion/branches/fs-successor-ids
> subversion/svn/merge-cmd.c:382: (apr_err=195016)
> subversion/libsvn_client/merge.c:11024: (apr_err=195016)
> subversion/libsvn_client/merge.c:10993: (apr_err=195016)
> subversion/libsvn_client/merge.c:10993: (apr_err=195016)
> subversion/libsvn_client/merge.c:10940: (apr_err=195016)
> subversion/libsvn_client/merge.c:10940: (apr_err=195016)
> svn: E195016: Reintegrate can only be used if revisions 880536 through 1181776 were previously merged from https://svn.apache.org/repos/asf/subversion/trunk to the reintegrate source, but this is not the case.
>
> subversion/libsvn_client/merge.c:10064: (apr_err=195016)
> subversion/libsvn_ra_serf/log.c:684: (apr_err=195016)
> subversion/libsvn_ra_serf/util.c:768: (apr_err=195016)
> subversion/libsvn_ra_serf/util.c:2118: (apr_err=195016)
> subversion/libsvn_ra_serf/util.c:2118: (apr_err=195016)
> subversion/libsvn_ra_serf/util.c:1850: (apr_err=195016)
> subversion/libsvn_ra_serf/util.c:1491: (apr_err=195016)
> subversion/libsvn_ra_serf/log.c:337: (apr_err=195016)
> subversion/libsvn_client/merge.c:9865: (apr_err=195016)
> svn: E195016: Working copy and merge source not ready for reintegration
>    0m4.43s real     0m1.64s user     0m0.17s system
> $
>
> So the error fits on the screen and appears after 4.5 seconds.
>
> Index: subversion/libsvn_client/merge.c
> ===================================================================
> --- subversion/libsvn_client/merge.c    (revision 1181756)
> +++ subversion/libsvn_client/merge.c    (working copy)
> @@ -9818,6 +9818,57 @@ typedef struct log_find_operative_baton_t
>   apr_pool_t *result_pool;
>  } log_find_operative_baton_t;
>
> +/* A svn_log_entry_receiver_t callback for find_unsynced_range().
> + * Returns SVN_ERR_CLIENT_NOT_READY_TO_MERGE if an unsynced revision
> + * is found. Else returns SVN_NO_ERROR. */
> +static svn_error_t *
> +log_find_unsynced_rev(void *baton,
> +                      svn_log_entry_t *log_entry,
> +                      apr_pool_t *pool)
> +{
> +  log_find_operative_baton_t *log_baton = baton;
> +  apr_hash_index_t *hi;
> +  svn_revnum_t revision;
> +
> +  revision = log_entry->revision;
> +
> +  for (hi = apr_hash_first(pool, log_entry->changed_paths2);
> +       hi;
> +       hi = apr_hash_next(hi))
> +    {
> +      const char *subtree_missing_this_rev;
> +      const char *path = svn__apr_hash_index_key(hi);
> +      const char *rel_path;
> +      const char *source_rel_path;
> +      svn_boolean_t in_catalog;
> +      svn_mergeinfo_t log_entry_as_mergeinfo;
> +
> +      rel_path = svn_fspath__skip_ancestor(log_baton->target_abspath, path);
> +      /* Easy out: The path is not within the tree of interest. */
> +      if (rel_path == NULL)
> +        continue;
> +
> +      source_rel_path = svn_relpath_join(log_baton->source_repos_rel_path,
> +                                         rel_path, pool);
> +
> +      SVN_ERR(svn_mergeinfo_parse(&log_entry_as_mergeinfo,
> +                                  apr_psprintf(pool, "%s:%ld",
> +                                               path, revision),
> +                                  pool));
> +
> +      SVN_ERR(mergeinfo_in_catalog(&in_catalog, &subtree_missing_this_rev,
> +                                   source_rel_path, log_entry_as_mergeinfo,
> +                                   revision, log_baton->merged_catalog,
> +                                   pool, pool));
> +
> +      if (!in_catalog)
> +        return svn_error_create(SVN_ERR_CLIENT_NOT_READY_TO_MERGE,
> +                                NULL, NULL);
> +    }
> +
> +  return SVN_NO_ERROR;
> +}
> +
>  /* A svn_log_entry_receiver_t callback for find_unsynced_ranges(). */
>  static svn_error_t *
>  log_find_operative_revs(void *baton,
> @@ -9934,6 +9985,109 @@ log_find_operative_revs(void *baton,
>         but based on the mergeinfo in MERGED_CATALOG, the change was
>         previously merged.
>
> +   Return SVN_ERR_CLIENT_NOT_READY_TO_MERGE if a revision is found which
> +   is not a phantom. Else, return no error.
> +
> +   Note: The keys in all mergeinfo catalogs used here are relative to the
> +   root of the repository.
> +
> +   Use SCRATCH_POOL for all temporary allocations. */
> +static svn_error_t *
> +find_unsynced_range(const char *source_repos_rel_path,
> +                    const char *target_repos_rel_path,
> +                    svn_mergeinfo_catalog_t unmerged_catalog,
> +                    svn_mergeinfo_catalog_t merged_catalog,
> +                    svn_ra_session_t *ra_session,
> +                    apr_pool_t *scratch_pool)
> +{
> +  apr_array_header_t *potentially_unmerged_ranges = NULL;
> +
> +  /* Convert all the unmerged history to a rangelist. */
> +  if (apr_hash_count(unmerged_catalog))
> +    {
> +      apr_hash_index_t *hi_catalog;
> +
> +      potentially_unmerged_ranges =
> +        apr_array_make(scratch_pool, 1, sizeof(svn_merge_range_t *));
> +
> +      for (hi_catalog = apr_hash_first(scratch_pool, unmerged_catalog);
> +           hi_catalog;
> +           hi_catalog = apr_hash_next(hi_catalog))
> +        {
> +          svn_mergeinfo_t mergeinfo = svn__apr_hash_index_val(hi_catalog);
> +          apr_hash_index_t *hi_mergeinfo;
> +          apr_pool_t *iterpool = svn_pool_create(scratch_pool);
> +
> +          for (hi_mergeinfo = apr_hash_first(scratch_pool, mergeinfo);
> +               hi_mergeinfo;
> +               hi_mergeinfo = apr_hash_next(hi_mergeinfo))
> +            {
> +              apr_array_header_t *rangelist =
> +                svn__apr_hash_index_val(hi_mergeinfo);
> +
> +              svn_pool_clear(iterpool);
> +              SVN_ERR(svn_rangelist_merge2(potentially_unmerged_ranges,
> +                                           rangelist, scratch_pool, iterpool));
> +            }
> +          svn_pool_destroy(iterpool);
> +        }
> +    }
> +
> +  /* Find any unmerged revisions which both affect the source and
> +     are not yet merged to it. */
> +  if (potentially_unmerged_ranges)
> +    {
> +      svn_revnum_t oldest_rev =
> +        (APR_ARRAY_IDX(potentially_unmerged_ranges,
> +                       0,
> +                       svn_merge_range_t *))->start + 1;
> +      svn_revnum_t youngest_rev =
> +        (APR_ARRAY_IDX(potentially_unmerged_ranges,
> +                       potentially_unmerged_ranges->nelts - 1,
> +                       svn_merge_range_t *))->end;
> +      apr_array_header_t *log_targets = apr_array_make(scratch_pool, 1,
> +                                                       sizeof(const char *));
> +      log_find_operative_baton_t log_baton;
> +
> +      log_baton.merged_catalog = merged_catalog;
> +      log_baton.unmerged_catalog = NULL;
> +      log_baton.source_repos_rel_path = source_repos_rel_path;
> +      log_baton.target_abspath = apr_psprintf(scratch_pool, "/%s",
> +                                              target_repos_rel_path);
> +      log_baton.result_pool = NULL;
> +
> +      APR_ARRAY_PUSH(log_targets, const char *) = "";
> +
> +      SVN_ERR(svn_ra_get_log2(ra_session, log_targets, youngest_rev,
> +                              oldest_rev, 0, TRUE, FALSE, FALSE,
> +                              NULL, log_find_unsynced_rev, &log_baton,
> +                              scratch_pool));
> +    }
> +
> +  return SVN_NO_ERROR;
> +}
> +
> +/* Determine if the mergeinfo on a reintegrate source SOURCE_REPOS_REL_PATH,
> +   reflects that the source is fully synced with the reintegrate target
> +   TARGET_REPOS_REL_PATH, even if a naive interpretation of the source's
> +   mergeinfo says otherwise -- See issue #3577.
> +
> +   UNMERGED_CATALOG represents the history (as mergeinfo) from
> +   TARGET_REPOS_REL_PATH that is not represented in SOURCE_REPOS_REL_PATH's
> +   explicit/inherited mergeinfo as represented by MERGED_CATALOG.
> +   MERGEINFO_CATALOG may be empty if the source has no explicit or inherited
> +   mergeinfo.
> +
> +   Using RA_SESSION, which is pointed at TARGET_REPOS_REL_PATH, check that all
> +   of the unmerged revisions in UNMERGED_CATALOG's mergeinfos are "phantoms",
> +   that is, one of the following conditions holds:
> +
> +     1) The revision affects no corresponding paths in SOURCE_REPOS_REL_PATH.
> +
> +     2) The revision affects corresponding paths in SOURCE_REPOS_REL_PATH,
> +        but based on the mergeinfo in MERGED_CATALOG, the change was
> +        previously merged.
> +
>    Make a deep copy, allocated in RESULT_POOL, of any portions of
>    UNMERGED_CATALOG that are not phantoms, to TRUE_UNMERGED_CATALOG.
>
> @@ -10631,7 +10785,6 @@ merge_reintegrate_locked(const char *source,
>   const char *url1, *url2;
>   svn_revnum_t rev1, rev2;
>   svn_mergeinfo_t unmerged_to_source_mergeinfo_catalog;
> -  svn_mergeinfo_t final_unmerged_catalog;
>   svn_mergeinfo_t merged_to_source_mergeinfo_catalog;
>   svn_boolean_t use_sleep = FALSE;
>   svn_error_t *err;
> @@ -10765,34 +10918,26 @@ merge_reintegrate_locked(const char *source,
>       /* Have we actually merged anything to the source from the
>          target?  If so, make sure we've merged a contiguous
>          prefix. */
> -      final_unmerged_catalog = apr_hash_make(scratch_pool);
> -
> -      SVN_ERR(find_unsynced_ranges(source_repos_rel_path,
> -                                   yc_ancestor_path,
> -                                   unmerged_to_source_mergeinfo_catalog,
> -                                   merged_to_source_mergeinfo_catalog,
> -                                   final_unmerged_catalog,
> -                                   target_ra_session, scratch_pool,
> -                                   scratch_pool));
> -
> -      if (apr_hash_count(final_unmerged_catalog))
> +      err = find_unsynced_range(source_repos_rel_path,
> +                                yc_ancestor_path,
> +                                unmerged_to_source_mergeinfo_catalog,
> +                                merged_to_source_mergeinfo_catalog,
> +                                target_ra_session, scratch_pool);
> +      if (err)
>         {
> -          svn_string_t *source_mergeinfo_cat_string;
> +          if (err->apr_err != SVN_ERR_CLIENT_NOT_READY_TO_MERGE)
> +            return svn_error_trace(err);
>
> -          SVN_ERR(svn_mergeinfo__catalog_to_formatted_string(
> -            &source_mergeinfo_cat_string,
> -            final_unmerged_catalog,
> -            "  ", "    Missing ranges: ", scratch_pool));
> -          return svn_error_createf(SVN_ERR_CLIENT_NOT_READY_TO_MERGE,
> -                                   NULL,
> -                                   _("Reintegrate can only be used if "
> -                                     "revisions %ld through %ld were "
> -                                     "previously merged from %s to the "
> -                                     "reintegrate source, but this is "
> -                                     "not the case:\n%s"),
> -                                   yc_ancestor_rev + 1, rev2,
> -                                   target_url,
> -                                   source_mergeinfo_cat_string->data);
> +          return svn_error_trace(
> +                   svn_error_quick_wrap(err,
> +                                        apr_psprintf(scratch_pool,
> +                                        _("Reintegrate can only be used if "
> +                                          "revisions %ld through %ld were "
> +                                          "previously merged from %s to the "
> +                                          "reintegrate source, but this is "
> +                                          "not the case.\n"),
> +                                          yc_ancestor_rev + 1, rev2,
> +                                          target_url)));
>         }
>     }
>
>
>

Re: O(n**3) behaviour in reintegrate merge

[Stefan Sperling <st...@elego.de>]

On Tue, Oct 11, 2011 at 03:05:11PM +0200, Stefan Sperling wrote:
> So while I think your fixes should be backported to 1.7.1 ASAP,
> I don't think the status quo is acceptable. How do we want to move
> forward?
> 
> For reference, here's the error message I'm getting:

Just to drive my point home, compare to this, which is what I get
with the patch below (I don't intend to commit this as it is, and
certainly not before this discussion has been resolved).

$ time svn merge --reintegrate ^/subversion/branches/fs-successor-ids
subversion/svn/merge-cmd.c:382: (apr_err=195016)
subversion/libsvn_client/merge.c:11024: (apr_err=195016)
subversion/libsvn_client/merge.c:10993: (apr_err=195016)
subversion/libsvn_client/merge.c:10993: (apr_err=195016)
subversion/libsvn_client/merge.c:10940: (apr_err=195016)
subversion/libsvn_client/merge.c:10940: (apr_err=195016)
svn: E195016: Reintegrate can only be used if revisions 880536 through 1181776 were previously merged from https://svn.apache.org/repos/asf/subversion/trunk to the reintegrate source, but this is not the case.

subversion/libsvn_client/merge.c:10064: (apr_err=195016)
subversion/libsvn_ra_serf/log.c:684: (apr_err=195016)
subversion/libsvn_ra_serf/util.c:768: (apr_err=195016)
subversion/libsvn_ra_serf/util.c:2118: (apr_err=195016)
subversion/libsvn_ra_serf/util.c:2118: (apr_err=195016)
subversion/libsvn_ra_serf/util.c:1850: (apr_err=195016)
subversion/libsvn_ra_serf/util.c:1491: (apr_err=195016)
subversion/libsvn_ra_serf/log.c:337: (apr_err=195016)
subversion/libsvn_client/merge.c:9865: (apr_err=195016)
svn: E195016: Working copy and merge source not ready for reintegration
    0m4.43s real     0m1.64s user     0m0.17s system
$

So the error fits on the screen and appears after 4.5 seconds.

Index: subversion/libsvn_client/merge.c
===================================================================
--- subversion/libsvn_client/merge.c	(revision 1181756)
+++ subversion/libsvn_client/merge.c	(working copy)
@@ -9818,6 +9818,57 @@ typedef struct log_find_operative_baton_t
   apr_pool_t *result_pool;
 } log_find_operative_baton_t;
 
+/* A svn_log_entry_receiver_t callback for find_unsynced_range().
+ * Returns SVN_ERR_CLIENT_NOT_READY_TO_MERGE if an unsynced revision
+ * is found. Else returns SVN_NO_ERROR. */
+static svn_error_t *
+log_find_unsynced_rev(void *baton,
+                      svn_log_entry_t *log_entry,
+                      apr_pool_t *pool)
+{
+  log_find_operative_baton_t *log_baton = baton;
+  apr_hash_index_t *hi;
+  svn_revnum_t revision;
+
+  revision = log_entry->revision;
+
+  for (hi = apr_hash_first(pool, log_entry->changed_paths2);
+       hi;
+       hi = apr_hash_next(hi))
+    {
+      const char *subtree_missing_this_rev;
+      const char *path = svn__apr_hash_index_key(hi);
+      const char *rel_path;
+      const char *source_rel_path;
+      svn_boolean_t in_catalog;
+      svn_mergeinfo_t log_entry_as_mergeinfo;
+
+      rel_path = svn_fspath__skip_ancestor(log_baton->target_abspath, path);
+      /* Easy out: The path is not within the tree of interest. */
+      if (rel_path == NULL)
+        continue;
+
+      source_rel_path = svn_relpath_join(log_baton->source_repos_rel_path,
+                                         rel_path, pool);
+
+      SVN_ERR(svn_mergeinfo_parse(&log_entry_as_mergeinfo,
+                                  apr_psprintf(pool, "%s:%ld",
+                                               path, revision),
+                                  pool));
+
+      SVN_ERR(mergeinfo_in_catalog(&in_catalog, &subtree_missing_this_rev,
+                                   source_rel_path, log_entry_as_mergeinfo,
+                                   revision, log_baton->merged_catalog,
+                                   pool, pool));
+
+      if (!in_catalog)
+        return svn_error_create(SVN_ERR_CLIENT_NOT_READY_TO_MERGE,
+                                NULL, NULL);
+    }
+
+  return SVN_NO_ERROR;
+}
+
 /* A svn_log_entry_receiver_t callback for find_unsynced_ranges(). */
 static svn_error_t *
 log_find_operative_revs(void *baton,
@@ -9934,6 +9985,109 @@ log_find_operative_revs(void *baton,
         but based on the mergeinfo in MERGED_CATALOG, the change was
         previously merged.
 
+   Return SVN_ERR_CLIENT_NOT_READY_TO_MERGE if a revision is found which
+   is not a phantom. Else, return no error.
+
+   Note: The keys in all mergeinfo catalogs used here are relative to the
+   root of the repository.
+
+   Use SCRATCH_POOL for all temporary allocations. */
+static svn_error_t *
+find_unsynced_range(const char *source_repos_rel_path,
+                    const char *target_repos_rel_path,
+                    svn_mergeinfo_catalog_t unmerged_catalog,
+                    svn_mergeinfo_catalog_t merged_catalog,
+                    svn_ra_session_t *ra_session,
+                    apr_pool_t *scratch_pool)
+{
+  apr_array_header_t *potentially_unmerged_ranges = NULL;
+
+  /* Convert all the unmerged history to a rangelist. */
+  if (apr_hash_count(unmerged_catalog))
+    {
+      apr_hash_index_t *hi_catalog;
+
+      potentially_unmerged_ranges =
+        apr_array_make(scratch_pool, 1, sizeof(svn_merge_range_t *));
+
+      for (hi_catalog = apr_hash_first(scratch_pool, unmerged_catalog);
+           hi_catalog;
+           hi_catalog = apr_hash_next(hi_catalog))
+        {
+          svn_mergeinfo_t mergeinfo = svn__apr_hash_index_val(hi_catalog);
+          apr_hash_index_t *hi_mergeinfo;
+          apr_pool_t *iterpool = svn_pool_create(scratch_pool);
+
+          for (hi_mergeinfo = apr_hash_first(scratch_pool, mergeinfo);
+               hi_mergeinfo;
+               hi_mergeinfo = apr_hash_next(hi_mergeinfo))
+            {
+              apr_array_header_t *rangelist =
+                svn__apr_hash_index_val(hi_mergeinfo);
+
+              svn_pool_clear(iterpool);
+              SVN_ERR(svn_rangelist_merge2(potentially_unmerged_ranges,
+                                           rangelist, scratch_pool, iterpool));
+            }
+          svn_pool_destroy(iterpool);
+        }
+    }
+
+  /* Find any unmerged revisions which both affect the source and
+     are not yet merged to it. */
+  if (potentially_unmerged_ranges)
+    {
+      svn_revnum_t oldest_rev =
+        (APR_ARRAY_IDX(potentially_unmerged_ranges,
+                       0,
+                       svn_merge_range_t *))->start + 1;
+      svn_revnum_t youngest_rev =
+        (APR_ARRAY_IDX(potentially_unmerged_ranges,
+                       potentially_unmerged_ranges->nelts - 1,
+                       svn_merge_range_t *))->end;
+      apr_array_header_t *log_targets = apr_array_make(scratch_pool, 1,
+                                                       sizeof(const char *));
+      log_find_operative_baton_t log_baton;
+
+      log_baton.merged_catalog = merged_catalog;
+      log_baton.unmerged_catalog = NULL;
+      log_baton.source_repos_rel_path = source_repos_rel_path;
+      log_baton.target_abspath = apr_psprintf(scratch_pool, "/%s",
+                                              target_repos_rel_path);
+      log_baton.result_pool = NULL;
+
+      APR_ARRAY_PUSH(log_targets, const char *) = "";
+
+      SVN_ERR(svn_ra_get_log2(ra_session, log_targets, youngest_rev,
+                              oldest_rev, 0, TRUE, FALSE, FALSE,
+                              NULL, log_find_unsynced_rev, &log_baton,
+                              scratch_pool));
+    }
+
+  return SVN_NO_ERROR;
+}
+
+/* Determine if the mergeinfo on a reintegrate source SOURCE_REPOS_REL_PATH,
+   reflects that the source is fully synced with the reintegrate target
+   TARGET_REPOS_REL_PATH, even if a naive interpretation of the source's
+   mergeinfo says otherwise -- See issue #3577.
+
+   UNMERGED_CATALOG represents the history (as mergeinfo) from
+   TARGET_REPOS_REL_PATH that is not represented in SOURCE_REPOS_REL_PATH's
+   explicit/inherited mergeinfo as represented by MERGED_CATALOG.
+   MERGEINFO_CATALOG may be empty if the source has no explicit or inherited
+   mergeinfo.
+
+   Using RA_SESSION, which is pointed at TARGET_REPOS_REL_PATH, check that all
+   of the unmerged revisions in UNMERGED_CATALOG's mergeinfos are "phantoms",
+   that is, one of the following conditions holds:
+
+     1) The revision affects no corresponding paths in SOURCE_REPOS_REL_PATH.
+
+     2) The revision affects corresponding paths in SOURCE_REPOS_REL_PATH,
+        but based on the mergeinfo in MERGED_CATALOG, the change was
+        previously merged.
+
    Make a deep copy, allocated in RESULT_POOL, of any portions of
    UNMERGED_CATALOG that are not phantoms, to TRUE_UNMERGED_CATALOG.
 
@@ -10631,7 +10785,6 @@ merge_reintegrate_locked(const char *source,
   const char *url1, *url2;
   svn_revnum_t rev1, rev2;
   svn_mergeinfo_t unmerged_to_source_mergeinfo_catalog;
-  svn_mergeinfo_t final_unmerged_catalog;
   svn_mergeinfo_t merged_to_source_mergeinfo_catalog;
   svn_boolean_t use_sleep = FALSE;
   svn_error_t *err;
@@ -10765,34 +10918,26 @@ merge_reintegrate_locked(const char *source,
       /* Have we actually merged anything to the source from the
          target?  If so, make sure we've merged a contiguous
          prefix. */
-      final_unmerged_catalog = apr_hash_make(scratch_pool);
-
-      SVN_ERR(find_unsynced_ranges(source_repos_rel_path,
-                                   yc_ancestor_path,
-                                   unmerged_to_source_mergeinfo_catalog,
-                                   merged_to_source_mergeinfo_catalog,
-                                   final_unmerged_catalog,
-                                   target_ra_session, scratch_pool,
-                                   scratch_pool));
-
-      if (apr_hash_count(final_unmerged_catalog))
+      err = find_unsynced_range(source_repos_rel_path,
+                                yc_ancestor_path,
+                                unmerged_to_source_mergeinfo_catalog,
+                                merged_to_source_mergeinfo_catalog,
+                                target_ra_session, scratch_pool);
+      if (err)
         {
-          svn_string_t *source_mergeinfo_cat_string;
+          if (err->apr_err != SVN_ERR_CLIENT_NOT_READY_TO_MERGE)
+            return svn_error_trace(err);
 
-          SVN_ERR(svn_mergeinfo__catalog_to_formatted_string(
-            &source_mergeinfo_cat_string,
-            final_unmerged_catalog,
-            "  ", "    Missing ranges: ", scratch_pool));
-          return svn_error_createf(SVN_ERR_CLIENT_NOT_READY_TO_MERGE,
-                                   NULL,
-                                   _("Reintegrate can only be used if "
-                                     "revisions %ld through %ld were "
-                                     "previously merged from %s to the "
-                                     "reintegrate source, but this is "
-                                     "not the case:\n%s"),
-                                   yc_ancestor_rev + 1, rev2,
-                                   target_url,
-                                   source_mergeinfo_cat_string->data);
+          return svn_error_trace(
+                   svn_error_quick_wrap(err,
+                                        apr_psprintf(scratch_pool,
+                                        _("Reintegrate can only be used if "
+                                          "revisions %ld through %ld were "
+                                          "previously merged from %s to the "
+                                          "reintegrate source, but this is "
+                                          "not the case.\n"),
+                                          yc_ancestor_rev + 1, rev2,
+                                          target_url)));
         }
     }